Circular perfect graphs

Abstract

Abstract 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

Locations

• Journal of Graph Theory - View
• CiteSeer X (The Pennsylvania State University) - View - PDF