Separating Polynomial χ-Boundedness from χ-Boundedness.

Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function f : N → N ∪ { ∞ } with f (1) = 1 and f (n) ⩾ 3 n + 1 3 , we construct a hereditary class of graphs G such that the maximum chromatic number of a graph in G with clique number n is equal to f(n) for every n ∈ N . In particular, we prove that there exist hereditary classes of graphs that are χ -bounded but not polynomially χ -bounded. [ABSTRACT FROM AUTHOR]