Detecting a long odd hole

DOI10.1007/S00493-020-4301-ZzbMATH Open1474.05218arXiv1904.12273OpenAlexW3107831848MaRDI QIDQ2035985FDOQ2035985

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour 

Publication date: 25 June 2021

Published in: Combinatorica (Search for Journal in Brave)

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.

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

zbMATH Keywords

induced cyclepolynomial-time algorithm

Mathematics Subject Classification ID

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

Cites Work

• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Proof of the Kalai-Meshulam conjecture
• Recognizing Berge graphs
• 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
• Three-in-a-tree in near linear time
• 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

Cited In (5)

• Finding a shortest even hole in polynomial time
• Detecting a long even hole
• Graphs of large chromatic number
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Detecting an Odd Hole

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)