Induced subgraphs of graphs of large K_{r}-free chromatic number

For an integer r>=2, the K_{r}-free chromatic number of a graph G, denoted by χ_{r}(G), is the minimum size of a partition of the set of vertices of G into parts each of which induces a K_{r}-free graph. In this setting, the K_{2}-free chromatic number is the usual chromatic number.

Which are the unavoidable induced subgraphs of graphs of large K_{r}-free chromatic number?

The notion of χ-boundedness, introduced by Gyárfás in the mid-1980s, captures when, for every induced subgraph of a graph, large chromatic number can occur only due to the presence of a sufficiently large complete subgraph. Generalizing the notion of χ-boundedness, we say that a hereditary class of graphs is χ_{r}-bounded if there exists a function which provides an upper bound for the K_{r}-free chromatic number of each graph of the class in terms of the graph's clique number.

With an emphasis on a generalization of the Gyárfás-Sumner conjecture for χ_{r}-bounded classes of graphs and on polynomial χ-boundedness, I will discuss some recent developments on χ_{r}-boundedness and related open problems.

Based on joint work with Taite LaGrange, Mathieu Rundström, and Sophie Spirkl