Circular perfect graphs

For 1 ≤  d  ≤  k , let K k/d be the graph with vertices 0, 1, …, k  − 1, in which i  ∼ j if d  ≤ | i  −  j | ≤  k  −  d . The circular chromatic number χ c ( G ) of a graph G is the minimum of those k/d for which G admits a homomorphism to K k/d . The circular clique number ω c ( G ) of G is the maximum of those k/d for which K k/d 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 prove that if G is circular perfect then for every vertex x of G , N G [ x ] is a perfect graph. Conversely, we prove that if for every vertex x of G , N G [ x ] is a perfect graph and G  −  N [ x ] is a bipartite graph with no induced P 5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj́os theorem for circular chromatic number for k/d  ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d  ≥ 3, starting from the graph K k/d , one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005