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

Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences,10.1016/j.jctb.2008.12.005,Journal of Combinatorial Theor

Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences   (Citations: 5)
BibTex | RIS | RefWorks Download
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.
Journal: Journal of Combinatorial Theory - JCT , vol. 99, no. 5, pp. 733-800, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: