Finding a shortest odd hole
An odd hole in a graph is an 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 algor...
Main Authors: | Chudnovsky, M, Scott, A, Seymour, P |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Association for Computing Machinery
2021
|
Similar Items
-
Detecting an odd hole
by: Chudnovsky, M, et al.
Published: (2020) -
Detecting a long odd hole
by: Chudnovsky, M, et al.
Published: (2020) -
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
by: Chudnovsky, M, et al.
Published: (2019) -
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
by: Chudnovsky, M, et al.
Published: (2019) -
Induced subgraphs of graphs with large chromatic number. I. Odd holes
by: Scott, A, et al.
Published: (2015)