Local structure of graphs of large K_r-free chromatic number

We denote by K_r the complete graph on r vertices. Let H be a graph. We say that a graph is H-free if it contains no induced subgraph isomorphic to H. 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? 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.