For 1 ≤
d ≤
k, let
Kk/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
Kk/d. The circular clique number ω
c(
G) of
G is the maximum of those
k/d for which
Kk/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,
NG[
x] is a perfect graph. Conversely, we prove that if for every vertex
x of
G,
NG[
x] is a perfect graph and
G ?
N[
x] is a bipartite graph with no induced
P5 (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
Kk/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
相似文献