On minimally circular-imperfect graphs |
| |
Authors: | Baogang Xu |
| |
Institution: | School of Mathematics and Computer Science, Nanjing Normal University, 122 Ninghai Road, Nanjing 210097, China |
| |
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: | 05c15 05c78 |
本文献已被 ScienceDirect 等数据库收录! |
|