Tutte Colloquium - Shenwei Huang

Title: Coloring (cap even hole)-free graphs

Abstract:

An even cycle of length 4 or more is called an even hole. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this talk we consider (cap, even hole)-free graphs, i.e., graphs that do not contain any even hole or cap as an induced subgraph. We first show how to decompose these graphs into (triangle, even hole)-free graphs. Using our decomposition theorem we prove that every such graph G has a vertex of degree at most 3/2 ω(G) − 1, and hence χ(G) ≤ 3/2 ω(G), where ω(G) denotes the size of a largest clique in G and χ(G) denotes the chromatic number of G. Finally, we give a polynomial-time algorithm for finding the chromatic number of these graphs. Our algorithm is based on our result that (triangle, even hole)-free graphs have tree-width at most 5.