Bounded twin-width graphs are polynomially \(χ\)-bounded

While the chromatic number \(\chi(G)\) of a graph \(G\) is at least its clique number \(\omega(G)\), it is a classical result that there exist triangle-free graphs with arbitrarily large chromatic number, so the chromatic number is in general not upper-bounded by a function of the clique number.

Let us say that a class of graphs is \(\chi\)-bounded if there is a function \(f\) such that for any graph \(G\) in the class, \(\chi(G)\le f(\omega(G))\). The paragraph above shows that the class of all graphs is not \(\chi\)-bounded. However a number of more restricted classes are \(\chi\)-bounded: This is the case for instance for perfect graphs (where equality holds), and more generally for graphs with no odd induced cycles of length at least \(\ell\), for any fixed \(\ell\) (as proved by Chudnovsky, Scott, Seymour, and Spirkl).

The Gyárfás-Sumner conjecture asserts that for any tree \(T\), the class of graphs which do not contain any induced copy of \(T\) is \(\chi\)-bounded. If the Gyárfás-Sumner conjecture was true, with a polynomial function \(f\) relating the clique and chromatic numbers, then this would directly imply another classical conjecture in the case of trees, the Erdős-Hajnal conjecture, which states that for any graph \(H\), every graph which does not contain any induced copy of \(H\) has a clique or stable set of polynomial size.

So let us say that a class of graphs is polynomially \(\chi\)-bounded if there is a polynomial \(f\) such that for any graph \(G\) in the class, \(\chi(G)\le f(\omega(G))\). Much less is known about polynomially \(\chi\)-bounded classes. It was only proved quite recently (by Briański, Davies, and Walczak) that there exist hereditary classes that are \(\chi\)-bounded but not polynomially \(\chi\)-bounded.

The present paper proves that any class of bounded twin-width is polynomially \(\chi\)-bounded. This extends an earlier result of Bonamy and Pilipczuk on graphs of bounded rankwidth. The proof heavily builds on a recent result of Pilipczuk and Sokołowski showing a quasi-polynomial bound (instead of a polynomial bound).

Classes of bounded twin-width are one of the most general classes of graphs which are known to be polynomially \(\chi\)-bounded. Bounded twin-width graphs (or structures) include proper minor-closed classes, graphs of bounded rankwidth, posets of bounded width, pattern-avoiding permutations, and some constructions of expander graph families. Any first-order interpretation or transduction of a class of bounded twin-width again has bounded twin-width, so for instance the class of all squares of planar graphs has bounded twin-width.