On recognition algorithms and structure of graphs with restricted induced cycles

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 types 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. In Chapter 3, we provide a structural description of all graphs that contain only holes of length ℓ for every ℓ ≥ 4.

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∈V(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 2003, Chudnovsky, Kawarabayashi and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019, Chudnovsky, Scott, Seymour and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year, Chudnovsky, Scott and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least ℓ for any fixed integer ℓ ≥ 5. In Chapter 2, we provide a polynomial-time algorithm to test whether a graph contains an even hole of length at least ℓ for any fixed integer ℓ ≥ 4.