On recognition algorithms and structure of graphs with restricted induced cycles

This is my PhD thesis which was defended in May 2021. 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škovíc 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 $\ell$ for every $\ell \geq 7$. 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 V(G)$. In 2002, Conforti, Cornuéjols, Kapoor and Vuškovíc 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 $\ell$ for any fixed integer $\ell \geq 5$. In Chapter 2, we provide a polynomial-time algorithm to test whether a graph contains an even hole of length at least $\ell$ for any fixed integer $\ell \geq 4$.