Detecting a long odd hole

DOI10.1007/S00493-020-4301-ZMaRDI QIDQ2035985zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Alex Scott, Paul 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

induced cyclepolynomial-time algorithm

Mathematics Subject Classification ID

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

Abstract: For each integer $tge5$, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $t$ and odd.

Cites work

• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Detecting an Odd Hole
• Finding an induced path that is not a shortest path
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• 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
• On the complexity of testing for odd holes and induced odd paths
• Proof of the Kalai-Meshulam conjecture
• Recognizing Berge graphs
• Three-in-a-tree in near linear time

Cited in

(7)

• Detecting a long even hole
• Detecting an Odd Hole
• Finding a shortest even hole in polynomial time
• Graphs of large chromatic number
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• The perfect divisibility and chromatic number of some odd hole-free graphs
• Improved algorithms for perfect graphs and odd holes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035985)