Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
Email: matdevos@math.princeton.edu

Luis Goddyn
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6
Email: goddyn@math.sfu.ca

Bojan Mohar
Affiliation: Department of Mathematics, University of Ljubljana, 1000 Ljubljana, Slovenia
Email: bojan.mohar@fmf.uni-lj.si

Dirk Vertigan
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918
Email: vertigan@math.lsu.edu

Xuding Zhu
Affiliation: Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan
Email: zhu@math.nsysu.edu.tw

DOI: http://dx.doi.org/10.1090/S0002-9947-04-03544-5
PII: S 0002-9947(04)03544-5
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