𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Structure and stability number of chair-, co-P- and gem-free graphs revisited

✍ Scribed by Andreas Brandstädt; Hoàng-Oanh Le; Jean-Marie Vanherpe

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
110 KB
Volume
86
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

The P 4 is the induced path with vertices a, b, c, d and edges ab, bc, cd. The chair (co-P, gem) has a fifth vertex adjacent to b (a and b, a, b, c and d, respectively). We give a complete structure description of prime chair-, co-P-and gem-free graphs which implies bounded clique width for this graph class. It is known that this has some nice consequences; very roughly speaking, every problem expressible in a certain kind of Monadic Second Order Logic (quantifying only over vertex set predicates) can be solved efficiently for graphs of bounded clique width. In particular, we obtain linear time for the problems Vertex Cover, Maximum Weight Stable Set (MWS), Maximum Weight Clique, Steiner Tree, Domination and Maximum Induced Matching on chair-, co-P-and gem-free graphs and a slightly larger class of graphs. This drastically improves a recently published O(n 4 ) time bound for Maximum Stable Set on butterfly-, chair-, co-P-and gem-free graphs.

📜 SIMILAR VOLUMES

On the structure and stability number of
On the structure and stability number of P5- and co-chair-free graphs
✍ Andreas Brandstädt; Raffaele Mosca 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 336 KB

We give a O(nm) time algorithm for the maximum weight stable set (MWS) problem on P5-and co-chair-free graphs without recognizing whether the (arbitrary) input graph is P5and co-chair-free. This algorithm is based on the fact that prime P5-and co-chair-free graphs containing 2K2 are matched co-bipar

(P5,diamond)-free graphs revisited: stru
(P5,diamond)-free graphs revisited: structure and linear time optimization
✍ Andreas Brandstädt 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 437 KB

Using the concept of prime graphs and modular decomposition of graphs, we give a complete structure description of (P5,diamond)-free graphs implying that these graphs have bounded clique width (the P5 is the induced path with ÿve vertices a; b; c; d; e and four edges ab; bc; cd; de, and the diamond

On the stability number of AH-free graph
On the stability number of AH-free graphs
✍ A. Hertz; D. de Werra 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 519 KB

## Abstract We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure that, at each step, builds from a graph __G__ a new graph __G^l^__ that has fewer nodes and has the property that α(__G^l^__) = α(__G__)