Graphs and Matroids Seminar - Sophie Spirkl and James Davies

Title: Two counterexamples related to chi-boundedness

Abstract:

This will be a joint talk with two parts.

Sophie Spirkl: I will present a counterexample to the following well-known conjecture: for every k, r, every graph G with clique number at most k and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least r. 

Joint work with Alvaro Carbonero, Patrick Hompe, and Benjamin Moore.

James Davies: We construct hereditary classes of graphs that are \chi-bounded but not polynomially \chi-bounded.

Joint work with Marcin Briański and Bartosz Walczak.