✦ LIBER ✦

Stability number of bull- and chair-free graphs

✍ Scribed by Caterina De Simone; Antonio Sassano

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 333 KB
Volume: 41
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(93)90032-j

No coin nor oath required. For personal study only.

📜 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 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

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

Stability number and chromatic number of

Stability number and chromatic number of tolerance graphs

✍ Giri Narasimhan; Rachel Manber 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 954 KB

Stability number and [a,b]-factors in gr

Stability number and [a,b]-factors in graphs

✍ Mekkia Kouider; Zbigniew Lonc 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract A spanning subgraph whose vertices have degrees belonging to the interval [__a,b__], where __a__ and __b__ are positive integers, such that __a__ ≤ __b__, is called an [__a,b__]‐factor. In this paper, we prove sufficient conditions for existence of an [__a,b__]‐factor, a connected [__a,

The stability number and connected -fact

The stability number and connected -factor in graphs

✍ Jiansheng Cai; Guizhen Liu; Jianfeng Hou 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 365 KB

Let G be a graph with vertex set V (G). In this work we present a sufficient condition for the existence of connected [k, k + 1]factors in graphs. The condition involves the stability number and degree conditions of graph G.