even-hole-free graph

{{Short description|Graph containing no induced cycles with an even number of nodes}}

File:Even-hole-free graph.svg of length 4 is possible in the first graph, making it an even-hole-free graph, but not an even-cycle-free graph. The second has no even cycles and so fits both categories.]]

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.{{citation |title=even-cycle--free graphs |url=https://www.graphclasses.org/classes/gc_706.html |access-date=2023-03-12 |website=www.graphclasses.org}}

{{harvtxt|Addario-Berry|Chudnovsky|Havet|Reed|2008}} demonstrated that every even-cycle-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 {{harvtxt|Chudnovsky|Seymour|2023}}, who gave a correct proof.

Recognition

{{harvtxt|Conforti|Cornuéjols|Kapoor|Vušković|2002b}} gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in ${\mathcal O}(n^{40})$ time.{{harvtxt|Conforti|Cornuéjols|Kapoor|Vušković|2002b}} present their algorithm and assert that it runs in polynomial time without giving an explicit analysis. {{harvtxt|Chudnovsky|Kawarabayashi|Seymour|2004}} estimate that it runs in "time about ${\mathcal O}(n^{40})$ ."

{{harvtxt|da Silva|Vušković|2008}} later improved this to ${\mathcal O}(n^{19})$ .

{{harvtxt|Chang|Lu|2012}} and {{harvtxt|Chang|Lu|2015}} improved this to ${\mathcal O}(n^{11})$ time.

The best currently known algorithm is given by {{harvtxt|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.{{harvtxt|Bienstock|1991}}

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.{{sfnp|Vušković|2010}}

Notes

References

{{citation

| last1 = Addario-Berry | first1 = Louigi

| last2 = Chudnovsky | first2 = Maria | author2-link = Maria Chudnovsky

| last3 = Havet | first3 = Frédéric

| last4 = Reed | first4 = Bruce | author4-link = Bruce Reed (mathematician)

| last5 = Seymour | first5 = Paul | author5-link = Paul Seymour (mathematician)

| title = Bisimplicial vertices in even-hole-free graphs

| journal = Journal of Combinatorial Theory | series=Series B

| volume = 98 | issue = 6 | year = 2008 | pages = 1119–1164

| doi = 10.1016/j.jctb.2007.12.006| doi-access = }}

{{citation

| last = Bienstock | first = Dan

| title = On the complexity of testing for odd holes and induced odd paths

| journal = Discrete Mathematics

| volume = 90 | issue = 1 | year = 1991 | pages = 85–92

| doi = 10.1016/0012-365X(91)90098-M| doi-access = free}}

{{citation

| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky

| last2 = Kawarabayashi | first2 = Ken-ichi | author2-link = Ken-ichi Kawarabayashi

| last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)

| title = Detecting even holes

| journal = Journal of Graph Theory

| volume = 48 | issue = 2 | year = 2004 | pages = 85–111

| doi = 10.1002/jgt.20040| s2cid = 2945499 }}

{{citation

| last1 = Conforti | first1 = Michele

| last2 = Cornuéjols | first2 = Gérard | author2-link = Gérard Cornuéjols

| last3 = Kapoor | first3 = Ajai

| last4 = Vušković | first4 = Kristina | author4-link = Kristina Vušković

| title = Even-hole-free graphs part I: Decomposition theorem

| journal = Journal of Graph Theory

| volume = 39 | issue = 1 | date = January 2002a | pages = 6–49

| doi = 10.1002/jgt.10006| s2cid = 12947855

| url = http://eprints.whiterose.ac.uk/74361/2/decomp-even.pdf

}}

{{citation

| last1 = Conforti | first1 = Michele

| last2 = Cornuéjols | first2 = Gérard | author2-link = Gérard Cornuéjols

| last3 = Kapoor | first3 = Ajai

| last4 = Vušković | first4 = Kristina | author4-link = Kristina Vušković

| title = Even-hole-free graphs part II: Recognition algorithm

| journal = Journal of Graph Theory

| volume = 40 | issue = 4 | date = August 2002b | pages = 238–266

| doi = 10.1002/jgt.10045| s2cid = 15044085

| url = http://eprints.whiterose.ac.uk/74360/2/algo-even.pdf

}}

{{citation

| last1 = da Silva | first1 = Murilo V.G.

| last2 = Vušković | first2 = Kristina | author2-link = Kristina Vušković

| year = 2008

| title = Decomposition of even-hole-free graphs with star cutsets and 2-joins

| url = http://www.comp.leeds.ac.uk/vuskovi/star.ps}}

{{citation

| last1 = Chang | first1 = Hsien-Chih

| last2 = Lu | first2 = Hsueh-I

| title = Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms

| chapter = A Faster Algorithm to Recognize Even-Hole-Free Graphs

| date = January 2012

| pages = 1286–1297

| doi = 10.1137/1.9781611973099.101

| isbn = 978-1-61197-210-8

| doi-access = free

| arxiv = 1311.0358

}}

{{citation

| last1 = Chang | first1 = Hsien-Chih

| last2 = Lu | first2 = Hsueh-I

| title = A Faster Algorithm to Recognize Even-Hole-Free Graphs

| date = July 2015 | journal = Journal of Combinatorial Theory, Series B

| volume = 113 | pages = 141–161

| doi = 10.1016/j.jctb.2015.02.001| arxiv = 1311.0358| s2cid = 1744497

}}

{{citation

| last = Vušković | first = Kristina | author-link = Kristina Vušković

| doi = 10.2298/AADM100812027V

| issue = 2

| journal = Applicable Analysis and Discrete Mathematics

| jstor = 43666110

| mr = 2724633

| pages = 219–240

| title = Even-hole-free graphs: a survey

| volume = 4

| year = 2010| url = http://eprints.whiterose.ac.uk/74347/2/ehfsurvey.pdf

}}

{{citation

| last1 = Lai | first1 = Kai-Yuan

| last2 = Lu | first2 = Hsueh-I

| last3 = Thorup | first3 = Mikkel | author3-link = Mikkel Thorup

| editor1-last = Makarychev | editor1-first = Konstantin

| editor2-last = Makarychev | editor2-first = Yury

| editor3-last = Tulsiani | editor3-first = Madhur

| editor4-last = Kamath | editor4-first = Gautam

| editor5-last = Chuzhoy | editor5-first = Julia | editor5-link = Julia Chuzhoy

| arxiv = 1909.07446

| contribution = Three-in-a-tree in near linear time

| doi = 10.1145/3357713.3384235

| pages = 1279–1292

| publisher = Association for Computing Machinery

| title = Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22–26, 2020

| title-link = Symposium on Theory of Computing

| year = 2020| isbn = 978-1-4503-6979-4

}}

{{citation

| title = Even-hole-free graphs still have bisimplicial vertices

| last1 = Chudnovsky | first1 = Maria

| last2 = Seymour | first2 = Paul

| journal = Journal of Combinatorial Theory, Series B

| year = 2023

| volume = 161 | pages = 331–381 | doi = 10.1016/j.jctb.2023.02.009

| url = https://www.sciencedirect.com/science/article/pii/S0095895623000151

| arxiv = 1909.10967

}}

External links

{{citation

| contribution-url = http://www.graphclasses.org/classes/gc_547.html

| contribution = Even-hole-free graphs

| url = http://www.graphclasses.org/index.html

| title = Information System on Graph Classes and their Inclusions}}

Category:Graph families