✦ LIBER ✦

Perfect graphs with unique P4-structure

✍ Scribed by Stefan Hougardy

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 635 KB
Volume: 165-166
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00188-4

No coin nor oath required. For personal study only.

✦ Synopsis

We will extend Reed's Semi-Strong Perfect Graph Theorem by proving that unbreakable c'ifree graphs different from a Ce and its complement have unique Ph-structure.

📜 SIMILAR VOLUMES

On the P4-structure of Perfect Graphs. I

On the P4-structure of Perfect Graphs. IV. Partner graphs

✍ Ryan B Hayward; William J Lenhart 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 318 KB

On the P4-structure of perfect graphs. I

On the P4-structure of perfect graphs. II. Odd decompositions

✍ C.T Hoang 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 897 KB

On the P4-structure of perfect graphs II

On the P4-structure of perfect graphs III. Partner decompositions

✍ V Chvátal 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 243 KB

On a unique tree representation for P4-e

On a unique tree representation for P4-extendible graphs

✍ B. Jamison; S. Olariu 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 944 KB

On theP4-Structure of Perfect Graphs V.

On theP4-Structure of Perfect Graphs V. Overlap Graphs

✍ Chı&#x0301;nh T. Hoàng; Stefan Hougardy; Frédéric Maffray 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 480 KB

Given a graph G we define its k-overlap graph as the graph whose vertices are the induced P 4 's of G and two vertices in the overlap graph are adjacent if the corresponding P 4 's in G have exactly k vertices in common. For k=1, 2, 3 we prove that if the k-overlap graph of G is bipartite then G is

Large P4-free graphs with bounded degree

✍ Myung S. Chung; Douglas B. West 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 424 KB

## Abstract Let __ex__ \* (__D__; __H__) denote the maximum number of edges in a connected graph with maximum degree __D__ and no induced subgraph isomorphic to __H.__ We prove that this is finite only when __H__ is a disjoint union of paths,m in which case we provide crude upper and lower bounds.