ON THE P-4-STRUCTURE OF PERFECT GRAPHS .5. OVERLAP GRAPHS

Authors
HOANG CT HOUGARDY S MAFFRAY F
Citation
Ct. Hoang et al., ON THE P-4-STRUCTURE OF PERFECT GRAPHS .5. OVERLAP GRAPHS, J COMB TH B, 67(2), 1996, pp. 212-237
Citations number
22
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
67
Issue
2
Year of publication
1996
Pages
212 - 237
Database
ISI
SICI code
0095-8956(1996)67:2<212:OTPOPG>2.0.ZU;2-O
Abstract
Given a graph G we define its k-overlap graph as the graph whose verti ces are the induced P-4's of G and two vertices in the overlap graph a re 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 bi partite then G is perfect. (C) 1996 Academic Press, Inc.