Title: Intersections of graphs and χ-boundedness: characterizing χ-guarding graph classes
| Speaker: | Hidde Koerts |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: For two graphs G1, G2, their intersection is given by only keeping the vertices and edges that appear in both. This graph operation is closely related to various intersection graph classes, such as the intersection graphs of axis-aligned rectangles. We are interested in the interplay between the graph intersection operation and χ-boundedness. A graph class C is χ-bounded if there exists a function providing an upper bound for the chromatic number of each graph in the class based on the graph’s clique number.
Specifically, we consider for which classes C1 it holds that for any hereditary χ-bounded class C2 the class resulting from taking the graph intersection of each pair of graphs from C1 and C2 is χ-bounded. We call such classes χ-guarding. In a previous talk, Aristotelis extensively introduced and motivated this topic, and shared some of the first results. In this follow-up talk, I will discuss further results on characterizing which hereditary classes are χ-guarding, focusing on classes defined by forbidding certain induced subgraphs.
This talk is based on joint work with Aristotelis Chaniotis, Rimma Hämäläinen, and Sophie Spirkl.