Definition of the circular chromatic number of a graph

Suppose G is a graph and r >= 2 is a real number. An r-coloring of G is a mapping f from V(G) to [0, r) such that for every edge xy of G,

1 <= | f(x) - f(y) | <= r-1.

We say G is r-colorable if G has an r-coloring. The circular chromatic number, chi_c(G), of G is defined as

 chi_c(G) = inf{r: G is r-colorable}.

Another equivalent definition of chi_c(G) is as follows:

Suppose p >= 2q are positive integers. A (p, q)-coloring of G is a mapping f from V(G) to {0, 1, ..., p-1} such that for each edge xy of G,

q <= | f(x) - f(y) | <= p-q.

Then

chi_c(G) = inf{p/q: G is (p, q)-colorable}.

Note that a (p, 1)-coloring of G is the same as the traditional p-coloring of G. Therefore

chi_c(G) <= chi(G).

On the other hand, it is not difficult to show that

chi(G) - 1 < chi_c(G).

So

chi(G) is equal to the ceiling of chi_c(G).