Burling Graphs in Graphs with Large Chromatic Number
Tara Abrishami, Marcin Briański, James Davies, Xiying Du, Jana Masaříková, Paweł Rzążewski, Bartosz Walczak · Society for Industrial and Applied Mathematics eBooks · 2026
A graph class is \(\chi\)-bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersection graphs of straight-line segments in the plane are \(\chi\)-bounded, but this was disproved by Pawlik et al. (2014), who showed another way to force large chromatic number in this class\(\unicode{x2014}\)by triangle-free graphs \(B_k\) with \(\chi(B_k) = k\) constructed by Burling (1965). This also disproved the celebrated conjecture of Scott (1997) that classes of graphs excluding induced subdivisions of a fixed graph are \(\chi\)-bounded.