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. More precisely, the definition may allow the graph to have induced cycles of length four, or may also disallow them: the latter is referred to as even-cycle-free graphs.^[1]

Addario-Berry et al. (2008) demonstrated that every even-hole-free graph contains a bisimplicial vertex (a vertex whose neighborhood is the union of two cliques), which settled a conjecture by Reed. The proof was later shown to be flawed by Chudnovsky & Seymour (2023), who gave a correct proof.

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.^[2] 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.^[3]

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.^[4]

Notes

↑ "even-cycle--free graphs", www.graphclasses.org, retrieved 2023-03-12
↑ 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, S2CID 2945499
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, S2CID 12947855
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, S2CID 15044085
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, arXiv:1311.0358, 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 (2020), "Three-in-a-tree in near linear time", in Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22–26, 2020, Association for Computing Machinery, pp. 1279–1292, arXiv:1909.07446, doi:10.1145/3357713.3384235
Chudnovsky, Maria; Seymour, Paul (2023), "Even-hole-free graphs still have bisimplicial vertices", Journal of Combinatorial Theory, Series B, arXiv:1909.10967, doi:10.1016/j.jctb.2023.02.009

External links

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] "even-cycle--free graphs", www.graphclasses.org, retrieved 2023-03-12

[2] 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})$ ."

[3] Bienstock (1991)

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

[1]

[2]

[3]

[4]