Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Coloring-flow duality of embedded graphs

Authors: Matt DeVos, Luis Goddyn, Bojan Mohar, Dirk Vertigan and Xuding Zhu
Journal: Trans. Amer. Math. Soc. 357 (2005), 3993-4016
MSC (2000): Primary 05C10, 05C15
Published electronically: August 11, 2004
MathSciNet review: 2159697
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05C10, 05C15

Retrieve articles in all journals with MSC (2000): 05C10, 05C15

Additional Information

Matt DeVos
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544

Luis Goddyn
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6

Bojan Mohar
Affiliation: Department of Mathematics, University of Ljubljana, 1000 Ljubljana, Slovenia

Dirk Vertigan
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918

Xuding Zhu
Affiliation: Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan

Keywords: Graph theory, coloring, flow, tension, local tension, circular chromatic number, surface, edge-width, triangulation, quadrangulation, locally bipartite.
Received by editor(s): April 7, 2003
Received by editor(s) in revised form: October 3, 2003
Published electronically: August 11, 2004
Additional Notes: The second author was supported in part by the National Sciences and Engineering Research Council of Canada, and the Pacific Institute for the Mathematical Sciences.
The third author was supported in part by the Ministry of Science and Technology of Slovenia, Research Program J1–0507–0101.
The fourth author was supported in part by the National Security Agency, grant number MDA904-01-0014.
The fifth author was supported in part by ROC National Science Council Grant NSC 91-2115-M-110-003.
Article copyright: © Copyright 2004 American Mathematical Society