2020/04/24 by Chudnovsky, Maria, Scott, Alex, Seymour, Paul
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2004.11874
An odd hole in a graph is a induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t, there is a polynomial time algorithm to test whether a graph contains an odd hole of length at least t. In this paper, we give an algorithm that finds a shortest odd hole, if one exists.