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

DOI:
https://doi.org/10.1090/S0002-9947-04-03544-5

Published electronically:
August 11, 2004

MathSciNet review:
2159697

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a directed graph embedded in a surface. A map is a *tension* if for every circuit , the sum of on the forward edges of is equal to the sum of on the backward edges of . If this condition is satisfied for every circuit of which is a contractible curve in the surface, then is a *local tension*. If holds for every , we say that is a (*local*) *-tension*. We define the *circular chromatic number* and the *local circular chromatic number* of by and , respectively. The invariant is a refinement of the usual chromatic number, whereas is closely related to Tutte's flow index and Bouchet's biflow index of the surface dual .

From the definitions we have . 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 and every , there exists an integer so that holds for every graph embedded in with edge-width at least , where the *edge-width* is the length of a shortest noncontractible circuit in .

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 , and thus in for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if is embedded in some surface with large edge-width and all its faces have even length , then . Similarly, if is a triangulation with large edge-width, then . 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.

**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 -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 -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**

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:
https://doi.org/10.1090/S0002-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