A talk by Bartosz Walczak, Jagiellonian University given on November 27, 2024.
A class of graphs 𝒢 is χ-bounded if there is a function f:ℕ→ℕ such that every graph in 𝒢 with chromatic number greater than f(k) contains a k-clique. Several important classes of graphs, including the class of string graphs and, more generally, every class of graphs excluding induced subdivisions of a fixed graph, are not χ-bounded because they contain a specific infinite family {Bℓ:ℓ∈ℕ} of triangle-free graphs with unbounded chromatic number, first constructed by Burling in 1965. We show that if 𝒢 is the class of string graphs or any 2-controlled class of graphs excluding induced subdivisions of a fixed graph, Burling's construction is the only reason for 𝒢 not being χ-bounded; that is, there is a function f:ℕ×ℕ→ℕ such that every graph in 𝒢 with chromatic number greater than f(k,ℓ) contains a k-clique or an induced copy of Bℓ. This (up to the “2-controlled” condition) confirms a conjecture of Chudnovsky, Scott, and Seymour from 2021. Being 2-controlled means that the chromatic number is bounded in terms of the maximum chromatic number of a ball of radius 2; this holds for string graphs and is conjectured to hold for every class of graphs excluding induced subdivisions of a fixed graph.
Joint work with Tara Abrishami, Marcin Briański, James Davies, Xiying Du, Jana Masaříková, and Paweł Rzążewski.