What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of \(\chi\)-bounded classes of graphs — classes where a large clique is essentially the only reason for large chromatic number.
Unfortunately, many interesting graph classes are not \(\chi\)-bounded. An eerily common obstruction to being \(\chi\)-bounded are the Burling graphs — a family of triangle-free graphs with unbounded chromatic number. These graphs have served as counterexamples in many settings: demonstrating that graphs excluding an induced subdivision of \(K_{5}\) are not \(\chi\)-bounded, that string graphs are not \(\chi\)-bounded, that intersection graphs of boxes in \({\mathbb{R}}^{3}\) are not \(\chi\)-bounded, and many others.
In many of these cases, this sequence is the only known obstruction to \(\chi\)-boundedness. This led Chudnovsky, Scott, and Seymour to conjecture that any graph of sufficiently high chromatic number must either contain a large clique, an induced proper subdivision of a clique, or a large Burling graph as an induced subgraph.
The prevailing belief was that this conjecture should be false. Somewhat surprisingly, we did manage to prove it under an extra assumption on the “locality” of the chromatic number — that the input graph belongs to a \(2\)-controlled family of graphs, where a high chromatic number is always certified by a ball of radius \(2\) with large chromatic number.
In this talk, I will present this result and discuss its implications in structural graph theory, and algorithmic implications to colouring problems in specific graph families.
This talk is based on joint work with Tara Abrishami, James Davies, Xiying Du, Jana Masaříková, Paweł Rzążewski, and Bartosz Walczak conducted during the STWOR2 workshop in Chęciny Poland.
|
