Premium
Families of graphs complete for the strong perfect graph Conjecture
Author(s) -
Corneil D. G.
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100106
Subject(s) - combinatorics , mathematics , conjecture , strong perfect graph theorem , graph , perfect graph , discrete mathematics , trivially perfect graph , chordal graph , pathwidth , 1 planar graph , line graph
The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true iff it is true on these restricted families. These appear to be the first results of this type.