Premium
On a Class of P 5 ‐Free Graphs
Author(s) -
Jamison B.,
Olariu S.
Publication year - 1989
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm198981133
Subject(s) - combinatorics , mathematics , conjecture , perfect graph , graph , cograph , induced subgraph , split graph , discrete mathematics , chordal graph , line graph , 1 planar graph , graph power , vertex (graph theory)
A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G , the chromatic number χ ( G′ ) equals the largest number ω ( G′ ) of pairwise adjacent vertices in G′ . The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement Ḡ contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P 5 ‐free graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom