Perfectness of the complements of circular complete graphs
Chao-Chi Yang · 2005
For p ≥ 2q, let Kp/q be the graph with vertices 0, 1, 2, . . . , p − 1 in which i ∼ j if q ≤ |i − j| ≤ p − q. The circular chromatic number χc(G) of a graph G is the minimum of those p/q for which G admits a homomorphism to Kp/q. The circular clique number ωc(G) of G is the maximum of those p/q for which Kp/q admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G we have χc(H) = ωc(H). In this paper, we characterize those rational numbers p/q for which Kp/q are circular perfect. We also prove that if G(n, S) is a circulant graph whose generating set S has cardinality at most 3, then G(n, S) is circular perfect.