- 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 r≥2, 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.