My thesis, in its broadest sense, is about the chromatic number of graphs. The main themes of the thesis are χ-boundedness and intersection graphs of geometrical objects, and a family of graphs which has applications in both: Burling graphs. Most of the results in my thesis are from [7, 9, 8] joint works with my supervisor, Nicolas Trotignon, and from [6].
The class of Burling graphs is a class of triangle-free graphs with arbitrarily large chromatic number. After Burling [1] defined these graphs in 1965, they have been widely used in research on intersection graphs (see for instance [4, 5]) and on χ-boundedness (see for instance [2, 3]).
The classical definition of Burling graphs is pretty long to describe here, and indeed my thesis starts by giving alternative equivalent definitions of Burling graphs. We give a totally combinatorial definition (called derived graphs), an axiomatic one (called abstract Burling graphs), and some geometric definitions, all equivalent and equal to the classical definition of Burling graphs.
After that, we study the structure of this class of graphs using the derived graph definition. In particular, we study the star cutsets in Burling graphs and we use these studies to state and prove a decomposition theorem for the class. We also prove several theorems about the holes and attachment of holes in Burling graphs.
Finally, we use the structural results to make progress in finding new graphs that are not weakly pervasive, an active field of research in χ-boundedness. We prove that many graphs, including K5 and some series-parallel graphs, are not weakly pervasive. We also provide the first such examples that contain star cutsets.
References
[1] James Perkins Burling. On coloring problems of families of polytopes, Ph.D. thesis. University of Colorado, Boulder, 1965.
[2] J´er´emie Chalopin, Louis Esperet, Zhentao Li, and Patrice Ossona de Mendez. Restricted frame graphs and a conjecture of Scott. The Electronic Journal of Combinatorics, 23(1), 2016.
[3] Tomasz Krawczyk, Arkadiusz Pawlik, and Bartosz Walczak. Coloring triangle-free rectangle overlap graphs with O(log log n) colors. Discrete & Computational Geometry, 53(1):199–220, 2014.
[4] Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Micha l Laso´n, Piotr Micek, William T Trotter, and Bartosz Walczak. Triangle-free geometric intersection graphs with large chromatic number. Discrete & Computational Geometry, 50(3):714–726, 2013.
[5] Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Micha l Laso´n, Piotr Micek, William T. Trotter, and Bartosz Walczak. Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory, Series B, 105:6–10, 2014.
[6] Pegah Pournajafi. Burling graphs as intersection graphs, 2022.
[7] Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part II: Structure, 2021.
[8] Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part III: Applications to χ-boundedness, 2021.
[9] Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part I: New characterizations. European Journal of Combinatorics, 110:103686, 2023.
Gratuit
Disciplines