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

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?)

  • 1. D. Archdeacon, J. Hutchinson, A. Nakamoto, S. Negami, and K. Ota, Chromatic numbers of quadrangulations on closed surfaces, J. Graph Theory 37 (2001) 100-114. MR 2002j:05044
  • 2. A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279-292. MR 85d:05109
  • 3. R. Brunet, B. Mohar, R. B. Richter, Separating and nonseparating disjoint homotopic cycles in graph embeddings, J. Combin. Theory Ser. B 66 (1996) 201-231. MR 96m:05060
  • 4. G. Chang, L. Huang, X. Zhu, Circular chromatic numbers of Mycielski's graphs, Discrete Math. 205 (1999) 23-37. MR 2000h:05077
  • 5. M. DeVos, Flows on bidirected graph, preprint.
  • 6. P. Erdos, Graph theory and probability, Canadian J. Math. 11 (1959) 34-38. MR 21:876
  • 7. S. Fisk, The nonexistence of colorings, J. Combin. Theory Ser. B 24 (1978) 247-248. MR 58:10562
  • 8. S. Fisk, B. Mohar, Coloring graphs without short non-bounding cycles, J. Combin. Theory Ser. B 60 (1994) 268-276. MR 95b:05073
  • 9. P. J. Giblin, Graphs, surfaces and homology. An introduction to algebraic topology, Second edition, Chapman and Hall, London-New York, 1981. MR 82m:55001
  • 10. J. Gimbel, C. Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), 4555-4564. MR 98i:05075
  • 11. L. Goddyn, The circular chromatic of even faced projective plane graphs, Preprint.
  • 12. L. A. Goddyn, M. Tarsi, C.-Q. Zhang, On $(k,d)$-colorings and fractional nowhere-zero flows, J. Graph Theory 28 (1998) 155-161. MR 99c:05063
  • 13. L. Goddyn, D. Vertigan, X. Zhu, Minty type formulas, preprint.
  • 14. M. de Graaf, A. Schrijver, Grid minors of graphs on the torus, J. Combin. Theory Ser. B 61 (1994) 57-62. MR 96c:05047
  • 15. M. J. Greenberg, J. R. Harper, Algebraic Topology. A First Course, Benjamin/Cummings Publ. Comp., Menlo Park, California, 1981. MR 83b:55001
  • 16. B. Grünbaum, Conjecture 6, in ``Recent Progress in Combinatorics'', Ed. W. T. Tutte, Academic Press, New York, 1969, p. 343. MR 40:4128
  • 17. J. P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory Ser. B 65 (1995) 139-155. MR 97d:05109
  • 18. J. Hutchinson, R. B. Richter, P. Seymour, Colouring Eulerian triangulations, J. Combin. Theory Ser. B 84 (2002) 225-239. MR 2003a:05052
  • 19. F. Jaeger, Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B 26 (1979) 205-216. MR 81j:05059
  • 20. F. Jaeger, Nowhere-zero flow problems, in, Selected Topics in Graph Theory, Volume 3, Academic Press, 1988, pp. 71-96. MR 93h:05003
  • 21. G. J. Minty, A theorem on $n$-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623-624.
  • 22. B. Mohar, Graph minors and graphs on surfaces, in ``Surveys in Combinatorics, 2001'', Ed. J. W. P. Hirschfeld, London Mathematical Society Lecture Note Series 288, Cambridge Univ. Press, Cambridge, 2001, pp. 145-163. MR 2002g:05173
  • 23. B. Mohar, P. D. Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser. B 84 (2002) 301-310. MR 2003b:05059
  • 24. B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001. MR 2002e:05050
  • 25. J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161-162. MR 16:1044b
  • 26. A. Nakamoto, S. Negami, K. Ota, Chromatic numbers and cycle partitions of quadrangulations on nonorientable surfaces, preprint.
  • 27. N. Robertson, P. D. Seymour, Graph minors VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45 (1988) 212-254. MR 89m:05072
  • 28. G. Ringel, Map Color Theorem, Springer-Verlag, New York-Heidelberg, 1974. MR 50:1955
  • 29. P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981) 130-135. MR 82j:05079
  • 30. C. Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001) 87-94. MR 2002g:05090
  • 31. C. Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993) 89-105. MR 94h:05031
  • 32. C. Thomassen, The chromatic number of a graph of girth 5 on a fixed surface. J. Combin. Theory Ser. B 87 (2003) 38-71.
  • 33. C. Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B 70 (1997) 67-100. MR 98k:05070
  • 34. W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80-91. MR 15:814c
  • 35. W. T. Tutte, A class of Abelian groups, Canad. J. Math. 8 (1956) 13-28. MR 17:708a
  • 36. D. A. Youngs, 4-chromatic projective graphs, J. Graph Theory 21 (1996) 219-227. MR 96h:05081
  • 37. X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371-410. MR 2002a:05116

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

American Mathematical Society