Separating polynomial chi-boundedness from chi-boundedness
Separating polynomial chi-boundedness from chi-boundedness
-
James Davies, University of Waterloo
Online Talk
We prove that for every function f that is lower-bounded by a certain cubic polynomial, there is a hereditary class of graphs F such that for every k > 1, the maximum chromatic number of a graph in F with clique number k is equal to f(k). This extends a recent breakthrough of Carbonero, Hompe, Moore, and Spirkl. In particular, this proves that there are hereditary classes of graphs that are chi-bounded but not polynomially chi-bounded. Joint work with Marcin Briański and Bartosz Walczak.