Coloring-flow duality of embedded graphs

Let be a directed graph embedded in a surface. A map is a tension if for every circuit , the sum of on the forward edges of is equal to the sum of on the backward edges of . If this condition is satisfied for every circuit of which is a contractible curve in the surface, then is a local tension. If holds for every , we say that is a (local) -tension. We define the circular chromatic number and the local circular chromatic number of by and , respectively. The invariant is a refinement of the usual chromatic number, whereas is closely related to Tutte's flow index and Bouchet's biflow index of the surface dual .

From the definitions we have . The main result of this paper is a far-reaching generalization of Tutte's coloring-flow duality in planar graphs. It is proved that for every surface and every , there exists an integer so that holds for every graph embedded in with edge-width at least , where the edge-width is the length of a shortest noncontractible circuit in .

In 1996, Youngs discovered that every quadrangulation of the projective plane has chromatic number 2 or 4, but never 3. As an application of the main result we show that such `bimodal' behavior can be observed in , and thus in for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if is embedded in some surface with large edge-width and all its faces have even length , then . Similarly, if is a triangulation with large edge-width, then . It is also shown that there exist Eulerian triangulations of arbitrarily large edge-width on nonorientable surfaces whose circular chromatic number is equal to 5.