𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On graphs without P5 and P5

✍ Scribed by Jean-Luc Fouquet; Vassilis Giakoumakis; Frédéric Maire; Henri Thuillier

Book ID
103060321
Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
588 KB
Volume
146
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We extend results due to Blfizsik et al. (1993) on graphs with no induced C4 and 2K2 to the self-complementary class of (P5, Ps)-free graphs. Moreover, we obtain an O(eJ 2) x-binding function for this last class of graphs, answering thus partially a question of A. Gyfirf~s.

📜 SIMILAR VOLUMES

Weighted parameters in (P5, P5)-free gra
Weighted parameters in (P5, P5)-free graphs
✍ Vassilis Giakoumakis; Irena Rusu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 488 KB

We use the modular decomposition to give O(n(m + n)) algorithms for finding a maximum weighted clique (respectively stable set) and an approximate weighted colouring (respectively partition into cliques) in a (&,E)-free graph. As a by-product, we obtain an O(m+n) algorithm for finding a minimum weig

A decomposition for a class of (P5,P̄5)-
A decomposition for a class of (P5,P̄5)-free graphs
✍ J.L. Fouquet 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 598 KB

Fouquet, J.L., A decomposition for a class of (P,, P,)-free graphs, Discrete Mathematics 121 (1993) 75-83. We give a decomposition for a subclass of (P5, P, )-free graphs, leading to an 0(n3) algorithm for the recognition of this class of graphs.