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.

Addario-Berry et al. (2008) demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.

Recognition

Conforti et al. (2002) gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in {\mathcal O}(n^{40}) time.[1] da Silva & Vušković (2008) later improved this to {\mathcal O}(n^{19}). The best currently known algorithm is given by Chang & Lu (2011) which runs in time {\mathcal O}(n^{11}).

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

Notes

  1. ↑ Conforti et al. (2002) 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})."
  2. ↑ Bienstock (1991)

References

External links