- Even-hole-free graph
In the mathematical area of
graph theory , a graph is even-hole-free if it contains noinduced cycle with an even number of vertices. Every even-hole-free graph contains abisimplicial vertex . [citation
last1 = Addario-Berry | first1 = Louigi
last2 = Chudnovsky | first2 = Maria
last3 = Havet | first3 = Frédéric
last4 = Reed | first4 = Bruce
last5 = Seymour | first5 = Paul | author5-link = Paul Seymour
title = Bisimplicial vertices in even-hole-free graphs
journal = Journal of Combinatorial Theory, Series B
year = In press
doi = 10.1016/j.jctb.2007.12.006 ]Recognition
harvtxt|Conforti|Cornuéjols|Kapoor|Vušković|2002 gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in time. [harvtxt|Conforti|Cornuéjols|Kapoor|Vušković|2002 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 ."] This was later improved to . [harvtxt|Chudnovsky|Kawarabayashi|Seymour|2004 give an algorithm and "sketch some improvements that bring the running time down to ."]
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]
Notes
References
* 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* citation
last1 = Chudnovsky | first1 = Maria
last2 = Kawarabayashi | first2 = Ken-ichi
last3 = Seymour | first3 = Paul | author3-link = Paul Seymour
title = Detecting even holes
journal =Journal of Graph Theory
volume = 48 | issue = 2 | year = 2004 | pages = 85–111
doi = 10.1002/jgt.20040* citation
last1 = Conforti | first1 = Michele
last2 = Cornuéjols | first2 = Gérard
last3 = Kapoor | first3 = Ajai
last4 = Vušković | first4 = Kristina
title = Even-hole-free graphs part I: Decomposition theorem
journal =Journal of Graph Theory
volume = 39 | issue = 1 | year = 2002 | pages = 6–49
doi = 10.1002/jgt.10006* citation
last1 = Conforti | first1 = Michele
last2 = Cornuéjols | first2 = Gérard
last3 = Kapoor | first3 = Ajai
last4 = Vušković | first4 = Kristina
title = Even-hole-free graphs part II: Recognition algorithm
journal =Journal of Graph Theory
volume = 40 | issue = 4 | year = 2002 | pages = 238–266
doi = 10.1002/jgt.10045External links
* cite web
url = http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_706.html
title = Graphclass: even-cycle-free
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]
Wikimedia Foundation. 2010.