Aristotelis Chaniotis, University of Waterloo

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.

See: https://sites.google.com/view/rutgersdmseminar