Graphs of bounded cliquewidth are polynomially $χ$-bounded

A trivial lower bound on the chromatic number of a graph is its clique number. In general, there is no upper bound on the chromatic number as a function of its clique number. Indeed, a famous result of Erdős establishes the existence of graphs with arbitrary large chromatic number and no triangle. However, well-structured classes of graphs may admit such a function: we say that a hereditary class of graphs, i.e., a class closed under taking induced subgraphs, is $\chi$-bounded if there exists a function $f$ such that the chromatic number of every graph in the class is at most $f(\omega)$, where $\omega$ is its clique number.

The most prominent $\chi$-bounded class of graphs is the class of perfect graphs, i.e., graphs $G$ such that the chromatic number of every induced subgraph of $G$ is equal to its clique number. Here, the function $f$ from the definition of $\chi$-bounded class is the identity. The Strong Perfect Graph Theorem of Chudnovsky, Robertson, Seymour and Thomas asserts that a graph is perfect if and only if it does not contain an odd cycle or its complement as an induced subgraph. Hence, perfect graphs include, among many other graph classes, interval graphs and more generally chordal graphs.

The authors consider graphs with bounded rank-width, or equivalently clique-width. Informally speaking, such graphs can be iteratively decomposed along simple structured cuts to single vertices. Decompositions along such cuts are assumed to play a key role in the characterization of graph classes closed under taking vertex minors analogously to the role of tree decompositions in the Graph Structure Theorem for graph classes closed under taking minors. Dvořák and Kráľ proved a conjecture of Geelen that every class of graphs with bounded rank-width is $\chi$-bounded, however, their function $f$ is exponential. The authors significantly improve this by showing that the function $f$ can be chosen to be polynomial and actually prove a more general statement concerning graphs decomposable along simple structured cuts to graphs from a polynomially $\chi$-bounded class. In the case of rank-width, the degree of the polynomial depends on the rank-width and this dependence is shown to be necessary.