Burling graphs and their generalizations

Zoom Link

In 1965, Burling constructed a sequence of triangle-free high-chromatic graphs that admit an intersection model by 3-dimensional boxes. In the last 12 years, Burling's construction has been used to solve several important problems in graph theory, most notably, to disprove Scott's conjecture on the chromatic number of graphs with excluded induced subdivisions. The class of graphs obtained from Burling's construction by taking all induced subgraphs, known as Burling graphs, has recently become a subject of study on its own. For instance, it is a minimal hereditary class of graphs with unbounded chromatic number—the only one known besides the "obvious" class of complete graphs. In this talk, I will present several points of view on Burling's construction, focusing or properties that make it different from other known constructions of triangle-free high-chromatic graphs. I will also present a generalization of Burling's construction that answers a recent question of Fox, Pach, and Suk, which is related to a 35-year-old conjecture that so-called k-quasi-planar graphs have linearly many edges. The latter is joint work with Aristotelis Chaniotis.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.