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. Every even-hole-free graph contains a bisimplicial 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 ${mathcal O}(n^{40})$ 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 ${mathcal O}(n^{40})$ ."] This was later improved to ${mathcal O}(n^{15})$ . [harvtxt|Chudnovsky|Kawarabayashi|Seymour|2004 give an ${mathcal O}(n^{31})$ algorithm and "sketch some improvements that bring the running time down to ${mathcal O}(n^{15})$ ."]

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

External 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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and … Wikipedia
Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… … Wikipedia
List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… … Wikipedia
Graphe cordal — Un cycle, en noir, avec deux cordes, en vert. Si l on s en tient à cette partie, le graphe est cordal. Supprimer l une des arêtes vertes rendrait le graphe non cordal. En effet, l autre arête verte formerait, avec les trois arêtes noires, un… … Wikipédia en Français
Induced path — An induced path of length four in a cube. Finding the longest induced path in a hypercube is known as the snake in the box problem. In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced… … Wikipedia
cosmos — /koz meuhs, mohs/, n., pl. cosmos, cosmoses for 2, 4. 1. the world or universe regarded as an orderly, harmonious system. 2. a complete, orderly, harmonious system. 3. order; harmony. 4. any composite plant of the genus Cosmos, of tropical… … Universalium
physical science, principles of — Introduction the procedures and concepts employed by those who study the inorganic world. physical science, like all the natural sciences, is concerned with describing and relating to one another those experiences of the surrounding… … Universalium
Criticism of Facebook — Facebook s growth as an Internet social networking site has met criticism on a range of issues, including online privacy, child safety, and the inability to terminate accounts without first manually deleting the content. In 2008, many companies… … Wikipedia
Glossary of cricket terms — Cricket is a team sport played between two teams of eleven. It is known for its rich terminology.[1][2][3] Some terms are often thought to be arcane and humorous by those not familiar with the game.[4] This is a general glossary of the… … Wikipedia
crystal — crystallike, adj. /kris tl/, n., adj., v., crystaled, crystaling or (esp. Brit.) crystalled, crystalling. n. 1. a clear, transparent mineral or glass resembling ice. 2. the transparent form of crystallized quartz. 3. Chem., Mineral. a solid body… … Universalium

Academic Dictionaries and Encyclopedias

Even-hole-free graph

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Even-hole-free graph

Look at other dictionaries:

Share the article and excerpts

Direct link