Minty characterized the chromatic number of a graph using acyclic orientations. Given an acyclic orientation D of G and a cycle C in G , let a(C) [ b(C) ] be the number of edges of C whose orientation in D is forward [backward]. Minty proved that if G has an orientation D such that a(C)/b(C) <= k-1 for every cycle C of G , then the chromatic number of G is at most k . Furthermore, the smallest such bound equals the chromatic number. Tuza strengthened this by showing that is suffices to consider only the cycles in G whose length is congruent to 1 modulo k.

A (k,d) -coloring of a graph assigns congruence classes mod k to the vertices so that adjacent vertices are assigned classes that are at least d apart. The circular chromatic number of G is the minimum of k/d such that G has a (k,d) -coloring. The ordinary chromatic number always equals the ceiling of the circular chromatic number.

At this summer's workshop in Vancouver, Zhu showed that if D is an acyclic orientation of G such that a(C)/b(C) <= k/d-1 for every cycle C of G whose length l satisfies (l-1)d == i mod k for i in k-d+1,...,0,...,d-1 , then the circular chromatic number of G is at most k/d . In this talk, we present the background and the proof of this theorem.