Combinatorics Seminar - Sophie Spirkl

16:15-18:00

Speaker: Sophie Spirkl

Title: New results on polynomial chi-boundedness

Abstract: The number of colours required to colour a graph G (the chromatic number chi(G)) is at least its clique number, that is, the maximum size of a set of pairwise adjacent vertices. A class of graphs is chi-bounded if the converse is approximately true, that is, the chromatic number is at most some function of the clique number. In this talk, we are interested in when this function can be chosen as a polynomial. I will discuss some recent results, mostly concerning the case of forbidding a single graph as an induced subgraph.