Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650535 | Discrete Mathematics | 2008 | 9 Pages |
Abstract
A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that Ïc(G-x)>Ï(G-x) for some xâV(G), then G=K(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Baogang Xu,