论文标题
找到一个最短的奇数
Finding a shortest odd hole
论文作者
论文摘要
图中的一个奇数是一个诱导的循环，奇数长度大于3。随后，我们表明，对于每个t，都有一个多项式时间算法来测试图是否包含至少t的奇数孔。在本文中，我们给出了一种算法，如果存在一个算法，则发现最短的奇数孔。
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.
