Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences

• Published in: Journal of combinatorial theory. Series B 2009-09, Vol.99 (5), p.733-800
• Main Authors: Kloks, Ton, Müller, Haiko, Vušković, Kristina
• Format: Article
• Language: English
• Subjects: Decomposition; Even-hole-free graphs; Greedy coloring algorithm; β-Perfect graphs; χ-Bounded families
• ISSN: 0095-8956; 1096-0902
• DOI: 10.1016/j.jctb.2008.12.005

In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e., chordless cycles of even length) and diamonds (i.e., a graph obtained from a clique of size 4 by removing an edge). We say that such graphs are (even-hole, diamond)-free. For this class of graphs we first obtain a decomposition theorem, using clique cutsets, bisimplicial cutsets (which is a special type of a star cutset) and 2-joins. This decomposition theorem is then used to prove that every graph that is (even-hole, diamond)-free contains a simplicial extreme (i.e., a vertex that is either of degree 2 or whose neighborhood induces a clique). This characterization implies that for every (even-hole, diamond)-free graph G, χ ( G ) ⩽ ω ( G ) + 1 (where χ denotes the chromatic number and ω the size of a largest clique). In other words, the class of (even-hole, diamond)-free graphs is a χ-bounded family of graphs with the Vizing bound for the chromatic number. The existence of simplicial extremes also shows that (even-hole, diamond)-free graphs are β-perfect, which implies a polynomial time coloring algorithm, by coloring greedily on a particular, easily constructable, ordering of vertices. Note that the class of (even-hole, diamond)-free graphs can also be recognized in polynomial time.