Even-hole-free graph

In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices.

Addario-Berry et al. (2008) demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.

Recognition

Conforti et al. (2002b) gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in ${\mathcal {O}}(n^{40})$ time.^[1] da Silva & Vušković (2008) later improved this to ${\mathcal {O}}(n^{19})$ . Chang & Lu (2012) and Chang & Lu (2015) improved this to ${\mathcal {O}}(n^{11})$ time. The best currently known algorithm is given by Lai, Lu & Thorup (2020) which runs in ${\mathcal {O}}(n^{9})$ time.

While even-hole-free graphs can be recognized in polynomial time, it is NP-complete to determine whether a graph contains an even hole that includes a specific vertex.^[2]

It is unknown whether graph coloring and the maximum independent set problem can be solved in polynomial time on even-hole-free graphs, or whether they are NP-complete. However the maximum clique can be found in even-hole-free graphs in polynomial time.^[3]

Notes

^ Conforti et al. (2002b) present their algorithm and assert that it runs in polynomial time without giving an explicit analysis. Chudnovsky, Kawarabayashi & Seymour (2004) estimate that it runs in "time about ${\mathcal {O}}(n^{40})$ ."
^ Bienstock (1991)
^ Vušković (2010).

References

Addario-Berry, Louigi; Chudnovsky, Maria; Havet, Frédéric; Reed, Bruce; Seymour, Paul (2008), "Bisimplicial vertices in even-hole-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1119–1164, doi:10.1016/j.jctb.2007.12.006
Bienstock, Dan (1991), "On the complexity of testing for odd holes and induced odd paths", Discrete Mathematics, 90 (1): 85–92, doi:10.1016/0012-365X(91)90098-M
Chudnovsky, Maria; Kawarabayashi, Ken-ichi; Seymour, Paul (2004), "Detecting even holes", Journal of Graph Theory, 48 (2): 85–111, doi:10.1002/jgt.20040
Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (January 2002a), "Even-hole-free graphs part I: Decomposition theorem" (PDF), Journal of Graph Theory, 39 (1): 6–49, doi:10.1002/jgt.10006
Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (August 2002b), "Even-hole-free graphs part II: Recognition algorithm" (PDF), Journal of Graph Theory, 40 (4): 238–266, doi:10.1002/jgt.10045
da Silva, Murilo V.G.; Vušković, Kristina (2008), Decomposition of even-hole-free graphs with star cutsets and 2-joins
Chang, Hsien-Chih; Lu, Hsueh-I (January 2012), "A Faster Algorithm to Recognize Even-Hole-Free Graphs", SODA '12: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms: 1286–1297, doi:10.1137/1.9781611973099.101, ISBN 978-1-61197-210-8
Chang, Hsien-Chih; Lu, Hsueh-I (July 2015), "A Faster Algorithm to Recognize Even-Hole-Free Graphs", Journal of Combinatorial Theory, Series B, 113: 141–161, arXiv:1311.0358, doi:10.1016/j.jctb.2015.02.001, S2CID 1744497
Vušković, Kristina (2010), "Even-hole-free graphs: a survey" (PDF), Applicable Analysis and Discrete Mathematics, 4 (2): 219–240, doi:10.2298/AADM100812027V, JSTOR 43666110, MR 2724633
Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (June 2020), "Three-in-a-Tree in Near Linear Time", STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing: 1279–1292, arXiv:1909.07446, doi:10.1145/3357713, ISBN 9781450369794

External links

"Even-hole-free graphs", Information System on Graph Classes and their Inclusions

[1] Conforti et al. (2002b) present their algorithm and assert that it runs in polynomial time without giving an explicit analysis. Chudnovsky, Kawarabayashi & Seymour (2004) estimate that it runs in "time about ${\mathcal {O}}(n^{40})$ ."

[2] Bienstock (1991)

[FOOTNOTEVušković2010-3] Vušković (2010).

[1]

[2]

[3]