Detecting a long odd hole

DOI10.1007/s00493-020-4301-zzbMath1474.05218arXiv1904.12273OpenAlexW3107831848MaRDI QIDQ2035985

Maria Chudnovsky, Alexander D. Scott, P. D. Seymour

Publication date: 25 June 2021

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.12273

zbMATH Keywords

polynomial-time algorithminduced cycle

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Detecting a long even hole ⋮ Finding a shortest even hole in polynomial time ⋮ Graphs of large chromatic number

Cites Work

• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Finding an induced path that is not a shortest path
• Proof of the Kalai-Meshulam conjecture
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
• Recognizing Berge graphs
• Detecting an Odd Hole
• Three-in-a-tree in near linear time

This page was built for publication: Detecting a long odd hole