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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2002-12, Vol.258 (1), p.347-351
Main Author: Xu, Baogang
Format: Article
Language:English
Subjects:
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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