𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the structure and stability number of P5- and co-chair-free graphs

✍ Scribed by Andreas Brandstädt; Raffaele Mosca

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
336 KB
Volume
132
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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-bipartite graphs and thus have very simple structure, and for 2K2-free graphs, there is a polynomial time algorithm for the MWS problem due to a result of Farber saying that 2K2-free graphs contain at most O(n 2 ) maximal stable sets. A similar argument can be used for (P5,co-P)-free graphs; their prime graphs are 2K2-free. Moreover, we give a complete classiÿcation of (P5,co-chair,H )-free graphs with respect to their clique width when H is a one-vertex P4 extension; this extends the characterization of (P5; P5,co-chair)-free graphs called semi-P4-sparse by Fouquet and Giakoumakis. For H being a house, P, bull or gem, the class of (P5,co-chair,H )-free graphs has bounded clique width and very simple structure whereas for the other four cases, namely H being a co-gem, chair, co-P or C5, the class has unbounded clique width due to a result of Makowsky and Rotics. Bounded clique width implies linear time algorithms for all algorithmic problems expressible in LinEMSOL-a variant of Monadic Second Order Logic including the MWS Problem.

📜 SIMILAR VOLUMES

Structure and stability number of chair-
Structure and stability number of chair-, co-P- and gem-free graphs revisited
✍ Andreas Brandstädt; Hoàng-Oanh Le; Jean-Marie Vanherpe 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 110 KB

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 gra

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__)

Sharp bounds on the order, size, and sta
Sharp bounds on the order, size, and stability number of graphs
✍ Pierre Hansen; Maolin Zheng 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

## Abstract We consider graphs __G = (V,E)__ with order ρ = |__V__|, size __e__ = |__E__|, and stability number β~0~. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © __1993 by John Wiley

On the asymptotic structure of sparse tr
On the asymptotic structure of sparse triangle free graphs
✍ Pr�mel, Hans J�rgen; Steger, Angelika 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 567 KB

An important result of Erdos, Kleitman, and Rothschild says that almost every triangle-free graph on n vertices has chromatic number 2. In this paper w e study the asymptotic structure of graphs in y0rb,,,(K3), i.e., in the class of trianglefree graphs on n vertices having rn = rn(n) edges. In parti

On the chromatic number of multiple inte
On the chromatic number of multiple interval graphs and overlap graphs
✍ A. Gyárfás 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Let x(G) and o(G) denote the chromatic number and clique number of a graph G. We prove that x can be bounded by a function of o for two well-known relatives of interval graphs. Multiple interval graphs (the intersection graphs of sets which can be written as the union of t closed intervals of a line