GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing en.wikipedia.org — Even-hole-free graph - Wikipedia 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.[1] Addario-Berry et al. (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 Chudnovsky & Seymour (2023), who gave a correct proof. RecognitionConforti et al. (2002b) gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in time.[2] da Silva & Vušković (2008) later improved this to . Chang & Lu (2012) and Chang & Lu (2015) improved this to time. The best currently known algorithm is given by Lai, Lu & Thorup (2020) which runs in 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.[3] 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.[4] Notes
References
External links |
| You are visitor 01402639 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |