Tutte Colloquium - Linda Cook

Title: Forbidding some induced cycles in a graph

Abstract:  We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain lengths in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković provided a structural description of the class of even-hole-free graphs.

Analysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex v in G. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2019, Chudnovsky, Scott, Seymour, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. In 2019, Chudnovsky, Scott, and Seymour strengthened this result by providing an O(n^(20k+40))-time algorithm to test whether a graph contains an odd hole of length at least k for every fixed integer k. Hajebi showed that it is W[1]-hard to test on input G, k whether G contains an even (or odd) hole of length at least k.

In this talk I will present an O(n^(9k + 3))-time algorithm to determine whether an input graph G has an even hole of length at least k for every fixed integer k (joint work with Paul Seymour). I will conclude the talk by describing the structure of all graphs that contain only holes of length k for every k ≥ 7 (joint work with Jake Horsfield, Myriam Preissmann, Paul Seymour, Ni Luh Dewi Sintiari, Cléophée Robin, Nicolas Trotignon, and Kristina Vušković).