Graphs and Matroids - Aristotelis Chaniotis

Title: Intersections of graphs and χ-boundedness: Interval graphs, chordal graphs, and χ-guarding graph classes

Abstract: Following A. Gyárfás (1987), we say that a hereditary class of graphs is χ-bounded if there exists a function which provides an upper bound for the chromatic number of each graph of the class in terms of the graph's clique number. In this terminology, E. Asplund and B.Grünbaum (1960),  motivated by a question of A. Bielecski (1948), proved that the class of intersection graphs of axis parallel rectangles is χ-bounded, and J. P. Burling, in his Ph.D. thesis (1965), proved that the class of intersection graphs of axis parallel boxes in R^3 is not χ-bounded. An interval graph is a graph which is isomorphic to the intersection graph of a family of intervals on a linearly ordered set (like the the real line); interval graphs are known to be perfect. Given a finite number of graphs, their intersection is the graph which has as vertex set (respectively edge set) the set of vertices (respectively the set of edges) which appear in all the given graphs. This operation can be naturally used to created new graph classes; we call the corresponding operation between graph classes: the graph-intersection of the classes. With this terminology the result of E. Asplund and B.Grünbaum states that the 2-fold graph-intersection of the class of interval graphs is χ-bounded, and the result of J. P. Burling states that the 3-fold graph-intersection of the class of interval graphs is not χ-bounded. In his seminal paper "Problems from the world surrounding perfect graphs" Gyárfás (1987) posed several questions regarding intersections of graphs and χ-boundedness, among these, motivated by the above results, he asked whether or not the graph-intersection of chordal graphs with interval graphs is χ-bounded. I will discuss results relevant to this question, and more generally results and questions concerning the interplay between intersections of graphs and χ-boundedness. The talk is based on joint work with Babak Miraftab, Rimma Hämäläinen, Hidde Koerts, and Sophie Spirkl.