Can I read Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences on EtoBox?

Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences by Ton Kloks; Haiko Müller; Kristina Vušković is a Computer Science article available to read on EtoBox.

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

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

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

Author

Ton Kloks; Haiko Müller; Kristina Vušković

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0095-8956)

Published

2009

Language

EN

Field

Computer Science (Physical Sciences)