Detecting a long even hole

DOI10.1016/j.ejc.2022.103537zbMath1490.05184arXiv2009.05691OpenAlexW3086596098MaRDI QIDQ2143407

Linda Cook, P. D. Seymour

Publication date: 31 May 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time algorithmcleaning list

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• The three-in-a-tree problem
• Detecting a long odd hole
• Proof of the Kalai-Meshulam conjecture
• A faster algorithm to recognize even-hole-free graphs
• Recognizing Berge graphs
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• Detecting a Theta or a Prism
• Detecting even holes
• Finding a Shortest Odd Hole
• Detecting an Odd Hole
• Three-in-a-tree in near linear time
• Algorithms for Perfectly Contractile Graphs
• Finding a shortest even hole in polynomial time