Seminar Details
Local Structure of Graphs of Large K_r-free Chromatic Number
- Start Date: April 22, 2024
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Aristotelis Chaniotis - University of Waterloo
- Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
For 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.
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 applications on polynomial χ-boundedness, I will discuss some recent developments on χ_r-boundedness and related open problems.
Based on joint work with Mathieu Rundström and Sophie Spirkl.