Detecting a long even hole

Linda Cook, Paul Seymour

Published 2020-09-12Version 1

For each integer $\ell \geq 4$, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $\ell$ and even