𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the stability number of AH-free graphs

✍ Scribed by A. Hertz; D. de Werra

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
519 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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) βˆ’ 1.

This new class of graphs is different from the known classes for which the stability number can be computed in polynomial time. Β© 1993 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

On the Number of Edges of Quadrilateral-
On the Number of Edges of Quadrilateral-Free Graphs
✍ ZoltΓ‘n FΓΌredi πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 247 KB

If a graph has q 2 +q+1 vertices (q>13), e edges and no 4-cycles then e 1 2 q(q+1) 2 . Equality holds for graphs obtained from finite projective planes with polarities. This partly answers a question of Erdo s from the 1930's. 1996 Academic Press, Inc. ## 1. Results Let f (n) denote the maximum n

On the choice number of claw-free perfec
On the choice number of claw-free perfect graphs
✍ Sylvain Gravier; FrΓ©dΓ©ric Maffray πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 273 KB

We prove that every 3-chromatic claw-free perfect graph is 3-choosable.

On the stability number of the edge inte
On the stability number of the edge intersection of two graphs
✍ Claudio Arbib; Alberto Caprara πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 38 KB

Let G be the graph obtained as the edge intersection of two graphs G 1 , G 2 on the same vertex set V . We show that if at , where Ξ±() is the cardinality of the largest stable set. Moreover, for general G 1 and G 2 , we show that Ξ±(G) R(Ξ±(G 1 ) + 1, Ξ±(G 2 ) + 1) -1, where R(k, ) is the Ramsey numbe