Cited By
View all- Cheong HLu H(2021)Finding a shortest even hole in polynomial timeJournal of Graph Theory10.1002/jgt.2274899:3(425-434)Online publication date: 24-Sep-2021
Finding a Shortest Odd Hole
Article No.: 13, Pages 1 - 21
Abstract
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 algorithm to test whether a graph contains an odd hole of length at least t. In this article, we give an algorithm that finds a shortest odd hole, if one exists.
References
[1]
Claude Berge. 1961. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114.
[2]
Daniel Bienstock. 1991. On the complexity of testing for odd holes and induced odd paths. Discrete Math. 90 (1991), 85--92.
[3]
Daniel Bienstock. 1992. Corrigendum: On the complexity of testing for odd holes and induced odd paths. Discrete Math. 102 (1992), 109.
[4]
Maria Chudnovsky, Gerard Cornuéjols, Xinming Liu, Paul Seymour, and Krisitna Vušković. 2005. Recognizing Berge graphs. Combinatorica 25 (2005), 143--186.
[5]
Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. 2006. The strong perfect graph theorem. Ann. Math. 164 (2006), 51--229.
[6]
Maria Chudnovsky, Alex Scott, and Paul Seymour. 2021. Detecting an long odd hole. Combinatorica 41 (2021), 1--30.
[7]
Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl. 2020. Detecting an odd hole. J. ACM 67 (2020), 1--12.
[8]
Andras Gyárfás. 1987. Problems from the world surrounding perfect graphs. In Proceedings of the International Conference on Combinatorial Analysis and Its Applications 19, 3--4 (1985), 413--441.
[9]
Alex Scott and Paul Seymour. 2016. Induced subgraphs of graphs with large chromatic number. I. Odd holes. J. Combin. Theor., Ser. B 121 (2016), 68--84.
Recommendations
Detecting an Odd Hole
We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.
Odd Hole Recognition in Graphs of Bounded Clique Size
In a graph $G$, an odd hole is an induced odd cycle of length at least 5. A clique of $G$ is a set of pairwise adjacent vertices. In this paper we consider the class ${\cal C}_k$ of graphs whose cliques have a size bounded by a constant $k$. Given a ...
Odd Induced Subgraphs in Planar Graphs with Large Girth
AbstractA long-standing conjecture asserts that there is a positive constant c such that every n-vertex graph without isolated vertices contains an induced subgraph with all degrees odd on at least cn vertices. Recently, Ferber and Krivelevich confirmed ...
Comments
Information & Contributors
Information
Published In
April 2021
235 pages
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 April 2021
Accepted: 01 January 2021
Revised: 01 November 2020
Received: 01 April 2020
Published in TALG Volume 17, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- NSF
- AFOSR
- U. S. Army Research Office
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 263Total Downloads
- Downloads (Last 12 months)95
- Downloads (Last 6 weeks)17
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
Cited By
View all- Cheong HLu H(2021)Finding a shortest even hole in polynomial timeJournal of Graph Theory10.1002/jgt.2274899:3(425-434)Online publication date: 24-Sep-2021
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in