𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences

✍ Scribed by Andreas Brandstädt; Vassilis Giakoumakis; Frédéric Maffray

Book ID
113564722
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
231 KB
Volume
160
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Complexity of clique-coloring odd-hole-f
Complexity of clique-coloring odd-hole-free graphs
✍ David Défossez 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐c

Even-hole-free graphs part I: Decomposit
Even-hole-free graphs part I: Decomposition theorem
✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB

## Abstract We prove a decomposition theorem for even‐hole‐free graphs. The decompositions used are 2‐joins and star, double‐star and triple‐star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even‐hole‐free graphs. © 2002 John Wiley &