Loading…
Two conjectures equivalent to the perfect graph conjecture
In this note, we study the graphs with the property that each of their induced subgraphs has circular clique number (defined in Section 2) the same as its clique number, prove that a graph satisfies such a property if and only if neither itself nor its complement contains an induced subgraph isomorp...
Saved in:
Published in: | Discrete mathematics 2002-12, Vol.258 (1), p.347-351 |
---|---|
Main Author: | |
Format: | Article |
Language: | English |
Subjects: | |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | In this note, we study the graphs with the property that each of their induced subgraphs has circular clique number (defined in Section 2) the same as its clique number, prove that a graph satisfies such a property if and only if neither itself nor its complement contains an induced subgraph isomorphic to an odd cycle of length at least five, and then give two conjectures which are equivalent to the perfect graph conjecture. |
---|---|
ISSN: | 0012-365X 1872-681X |
DOI: | 10.1016/S0012-365X(02)00403-X |