Coloring-flow duality of embedded graphs

Let $G$ be a directed graph embedded in a surface. A map $\phi : E(G) \rightarrow \mathbb{R}$ is a tension if for every circuit $C \subseteq G$, the sum of $\phi$ on the forward edges of $C$ is equal to the sum of $\phi$ on the backward edges of $C$. If this condition is satisfied for every circuit of $G$ which is a contractible curve in the surface, then $\phi$ is a local tension. If $1 \le \vert\phi(e)\vert \le \alpha-1$ holds for every $e \in E(G)$, we say that $\phi$ is a (local) $\alpha$-tension. We define the circular chromatic number and the local circular chromatic number of $G$ by $\chi_{\rm c}(G) =\inf \{\alpha \in \mathbb{R}\mid \mbox{$G$ has an $\alpha$ -tension} \}$and $\chi_{\rm loc}(G) = \inf \{ \alpha \in \mathbb{R}\mid \mbox{$G$\space has a local $\alpha$ -tension} \}$, respectively. The invariant $\chi_{\rm c}$ is a refinement of the usual chromatic number, whereas $\chi_{\rm loc}$ is closely related to Tutte's flow index and Bouchet's biflow index of the surface dual $G^*$.

From the definitions we have $\chi_{\rm loc}(G) \le \chi_{\rm c}(G)$. 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 $\mathbb{X}$ and every $\varepsilon > 0$, there exists an integer $M$ so that $\chi_{\rm c}(G) \le \chi_{\rm loc}(G)+\varepsilon$ holds for every graph embedded in $\mathbb{X}$ with edge-width at least $M$, where the edge-width is the length of a shortest noncontractible circuit in $G$.

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 $\chi_{\rm loc}$, and thus in $\chi_{\rm c}$for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if $G$ is embedded in some surface with large edge-width and all its faces have even length $\le 2r$, then $\chi_{\rm c}(G)\in [2,2+\varepsilon] \cup [\frac{2r}{r-1},4]$. Similarly, if $G$ is a triangulation with large edge-width, then $\chi_{\rm c}(G)\in [3,3+\varepsilon] \cup [4,5]$. 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.