Surf Wiki
Save to docs
general/graph-families

From Surf Wiki (app.surf) — the open knowledge base

Even-hole-free graph

Graph containing no induced cycles with an even number of nodes

Even-hole-free graph
Summary

Graph containing no induced cycles with an even number of nodes

An [[induced cycle]] 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.

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 , who gave a correct proof.

Recognition

gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in {\mathcal O}(n^{40}) time. later improved this to {\mathcal O}(n^{19}). and improved this to {\mathcal O}(n^{11}) time. The best currently known algorithm is given by 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.

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.

Notes

References

  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation | doi-access = free
  • {{citation
  • {{citation
  • {{citation | 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 | title-link = Symposium on Theory of Computing
  • {{citation

References

  1. "even-cycle--free graphs".
  2. {{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})."
  3. {{harvtxt. Bienstock. 1991
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

graph-families
Want to explore this topic further?

Ask Mako anything about Even-hole-free graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report