Induced subgraphs of graphs of large K_r-free chromatic number (Aristotelis Chaniotis)

Series
Graph Theory Seminar
Time
Tuesday, November 26, 2024 - 3:30pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Aristotelis Chaniotis – University of Waterloo – https://www.aristotelischaniotis.info/
Organizer
Evelyne Smith-Roberge

For an integer r2, the Kr-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 Kr-free graph. In this setting, the K2-free chromatic number is the usual chromatic number.

Which are the unavoidable induced subgraphs of graphs of large Kr-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 Kr-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\'arf\'as-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 Mathieu Rundstr\"om and Sophie Spirkl, and with Bartosz Walczak.