Output details
11 - Computer Science and Informatics
University of Leeds
Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
<13>Even-hole-free graphs are studied because they relate to (beta-)perfect graphs. We substantially strengthen known methods to decompose (even-hole,diamond)-free graphs. This enables us to prove that these graphs are beta-perfect. Only now one can apply all known results on beta-perfect graphs to (even-hole,diamond)-free graphs. This paper was the most downloaded article from JCT(B) in the month it appeared:
http://top25.sciencedirect.com/subject/mathematics/16/journal/journal-of-combinatorial-theory-series-b/00958956/archive/23/.
Subsequently, Vušković and da Silva extended our decomposition to all even-hole-free graphs (analogously to the famous decomposition of perfect graphs), leading to the fastest known recognition algorithm for that class (2012).