Coloring-flow duality of embedded graphs
HTML articles powered by AMS MathViewer
- by Matt DeVos, Luis Goddyn, Bojan Mohar, Dirk Vertigan and Xuding Zhu PDF
- Trans. Amer. Math. Soc. 357 (2005), 3993-4016 Request permission
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 |\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.References
- Dan Archdeacon, Joan Hutchinson, Atsuhiro Nakamoto, Seiya Negam, and Katsuhiro Ota, Chromatic numbers of quadrangulations on closed surfaces, J. Graph Theory 37 (2001), no. 2, 100–114. MR 1829924, DOI 10.1002/jgt.1005
- A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983), no. 3, 279–292. MR 714451, DOI 10.1016/0095-8956(83)90041-2
- Richard Brunet, Bojan Mohar, and R. Bruce Richter, Separating and nonseparating disjoint homotopic cycles in graph embeddings, J. Combin. Theory Ser. B 66 (1996), no. 2, 201–231. MR 1376046, DOI 10.1006/jctb.1996.0016
- Gerard J. Chang, Lingling Huang, and Xuding Zhu, Circular chromatic numbers of Mycielski’s graphs, Discrete Math. 205 (1999), no. 1-3, 23–37. MR 1703312, DOI 10.1016/S0012-365X(99)00033-3
- M. DeVos, Flows on bidirected graph, preprint.
- P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
- Steve Fisk, The nonexistence of colorings, J. Combinatorial Theory Ser. B 24 (1978), no. 2, 247–248. MR 491299, DOI 10.1016/0095-8956(78)90028-x
- Steve Fisk and Bojan Mohar, Coloring graphs without short nonbounding cycles, J. Combin. Theory Ser. B 60 (1994), no. 2, 268–276. MR 1271274, DOI 10.1006/jctb.1994.1018
- P. J. Giblin, Graphs, surfaces and homology, 2nd ed., Chapman and Hall Mathematics Series, Chapman & Hall, London-New York, 1981. An introduction to algebraic topology. MR 643363
- John Gimbel and Carsten Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), no. 11, 4555–4564. MR 1422897, DOI 10.1090/S0002-9947-97-01926-0
- L. Goddyn, The circular chromatic of even faced projective plane graphs, Preprint.
- Luis A. Goddyn, Michael Tarsi, and Cun-Quan Zhang, On $(k,d)$-colorings and fractional nowhere-zero flows, J. Graph Theory 28 (1998), no. 3, 155–161. MR 1626816, DOI 10.1002/(SICI)1097-0118(199807)28:3<155::AID-JGT5>3.0.CO;2-J
- L. Goddyn, D. Vertigan, X. Zhu, Minty type formulas, preprint.
- Maurits de Graaf and Alexander Schrijver, Grid minors of graphs on the torus, J. Combin. Theory Ser. B 61 (1994), no. 1, 57–62. MR 1275263, DOI 10.1006/jctb.1994.1029
- Marvin J. Greenberg and John R. Harper, Algebraic topology, Mathematics Lecture Note Series, vol. 58, Benjamin/Cummings Publishing Co., Inc., Advanced Book Program, Reading, Mass., 1981. A first course. MR 643101
- W. T. Tutte (ed.), Recent progress in combinatorics, Academic Press, New York-London, 1969. MR 0250896
- Joan P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory Ser. B 65 (1995), no. 1, 139–155. MR 1347344, DOI 10.1006/jctb.1995.1047
- Joan Hutchinson, R. Bruce Richter, and Paul Seymour, Colouring Eulerian triangulations, J. Combin. Theory Ser. B 84 (2002), no. 2, 225–239. MR 1889255, DOI 10.1006/jctb.2001.2074
- F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979), no. 2, 205–216. MR 532588, DOI 10.1016/0095-8956(79)90057-1
- Lowell W. Beineke and Robin J. Wilson (eds.), Selected topics in graph theory. 3, Academic Press, Inc., San Diego, CA, 1988. MR 1205394
- G. J. Minty, A theorem on $n$-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623-624.
- Bojan Mohar, Graph minors and graphs on surfaces, Surveys in combinatorics, 2001 (Sussex), London Math. Soc. Lecture Note Ser., vol. 288, Cambridge Univ. Press, Cambridge, 2001, pp. 145–163. MR 1850707
- Bojan Mohar and Paul D. Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser. B 84 (2002), no. 2, 301–310. MR 1889261, DOI 10.1006/jctb.2001.2086
- Bojan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. MR 1844449
- Tadasi Nakayama, On Frobeniusean algebras. I, Ann. of Math. (2) 40 (1939), 611–633. MR 16, DOI 10.2307/1968946
- A. Nakamoto, S. Negami, K. Ota, Chromatic numbers and cycle partitions of quadrangulations on nonorientable surfaces, preprint.
- Neil Robertson and P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45 (1988), no. 2, 212–254. MR 961150, DOI 10.1016/0095-8956(88)90070-6
- Gerhard Ringel, Map color theorem, Die Grundlehren der mathematischen Wissenschaften, Band 209, Springer-Verlag, New York-Heidelberg, 1974. MR 0349461
- P. D. Seymour, Nowhere-zero $6$-flows, J. Combin. Theory Ser. B 30 (1981), no. 2, 130–135. MR 615308, DOI 10.1016/0095-8956(81)90058-7
- Claude Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001), no. 2, 87–94. MR 1857769, DOI 10.1002/jgt.1025
- Carsten Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), no. 1, 89–105. MR 1234386, DOI 10.1006/jctb.1993.1057
- C. Thomassen, The chromatic number of a graph of girth 5 on a fixed surface. J. Combin. Theory Ser. B 87 (2003) 38–71.
- Carsten Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B 70 (1997), no. 1, 67–100. MR 1441260, DOI 10.1006/jctb.1996.1722
- Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
- Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
- D. A. Youngs, $4$-chromatic projective graphs, J. Graph Theory 21 (1996), no. 2, 219–227. MR 1368748, DOI 10.1002/(SICI)1097-0118(199602)21:2<219::AID-JGT12>3.0.CO;2-E
- Xuding Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001), no. 1-3, 371–410. Combinatorics, graph theory, algorithms and applications. MR 1815614, DOI 10.1016/S0012-365X(00)00217-X
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
- MR Author ID: 126065
- ORCID: 0000-0002-7408-6148
- 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
- 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. - © Copyright 2004 American Mathematical Society
- 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
- MathSciNet review: 2159697