Coloring-flow duality of embedded graphs
Matt DeVos, Luis Goddyn, Bojan Mohar, Dirk Vertigan, Xuding Zhu · Transactions of the American Mathematical Society · 2004
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 |\phi (e)| \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 _{\mathrm {c}}(G) =\inf \{ \alpha \in \mathbb {R} \mid {}$ $G$ has an $\alpha$-tension$\}$ and $\chi _{\operatorname {loc}}(G) = \inf \{ \alpha \in \mathbb {R} \mid {}$ $G$ has a local $\alpha$-tension$\}$, respectively. The invariant $\chi _{\mathrm {c}}$ is a refinement of the usual chromatic number, whereas $\chi _{\operatorname {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 _{\operatorname {loc}}(G) \le \chi _{\mathrm {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 _{\mathrm {c}}(G) \le \chi _{\operatorname {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 _{\operatorname {loc}}$, and thus in $\chi _{\mathrm {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 _{\mathrm {c}}(G)\in [2,2+\varepsilon ] \cup [\frac {2r}{r-1},4]$. Similarly, if $G$ is a triangulation with large edge-width, then $\chi _{\mathrm {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.