Hyperbolic families and coloring graphs on surfaces
HTML articles powered by AMS MathViewer
- by Luke Postle and Robin Thomas HTML | PDF
- Trans. Amer. Math. Soc. Ser. B 5 (2018), 167-221
Abstract:
We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $G$ be a graph embedded in a fixed surface $\Sigma$ of genus $g$ and let $L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $G$ is triangle-free, or each list has size at least three and $G$ has no cycle of length four or less. An $L$-coloring of $G$ is a mapping $\phi$ with domain $V(G)$ such that $\phi (v)\in L(v)$ for every $v\in V(G)$ and $\phi (v)\ne \phi (u)$ for every pair of adjacent vertices $u,v\in V(G)$. We prove
if every non-null-homotopic cycle in $G$ has length $\Omega (\log g)$, then $G$ has an $L$-coloring,
if $G$ does not have an $L$-coloring, but every proper subgraph does (“$L$-critical graph”), then $|V(G)|=O(g)$,
if every non-null-homotopic cycle in $G$ has length $\Omega (g)$, and a set $X\subseteq V(G)$ of vertices that are pairwise at distance $\Omega (1)$ is precolored from the corresponding lists, then the precoloring extends to an $L$-coloring of $G$,
if every non-null-homotopic cycle in $G$ has length $\Omega (g)$, and the graph $G$ is allowed to have crossings, but every two crossings are at distance $\Omega (1)$, then $G$ has an $L$-coloring,
if $G$ has at least one $L$-coloring, then it has at least $2^{\Omega (|V(G)|)}$ distinct $L$-colorings.
We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.
References
- V. A. Aksenov, The extension of a $3$-coloring on planar graphs, Diskret. Analiz 26, Grafy i Testy (1974), 3–19, 84 (Russian). MR 543788
- Michael O. Albertson, You can’t paint yourself into a corner, J. Combin. Theory Ser. B 73 (1998), no. 2, 189–194. MR 1632011, DOI 10.1006/jctb.1998.1827
- Michael O. Albertson and Joan P. Hutchinson, The three excluded cases of Dirac’s map-color theorem, Second International Conference on Combinatorial Mathematics (New York, 1978) Ann. New York Acad. Sci., vol. 319, New York Acad. Sci., New York, 1979, pp. 7–17. MR 556001
- Michael O. Albertson and Joan P. Hutchinson, Extending colorings of locally planar graphs, J. Graph Theory 36 (2001), no. 2, 105–116. MR 1805498, DOI 10.1002/1097-0118(200102)36:2<105::AID-JGT5>3.3.CO;2-8
- Michael O. Albertson and Joan P. Hutchinson, Graph color extensions: when Hadwiger’s conjecture and embeddings help, Electron. J. Combin. 9 (2002), no. 1, Research Paper 37, 10. MR 1928789
- Michael O. Albertson and Joan P. Hutchinson, Extending precolorings of subgraphs of locally planar graphs, European J. Combin. 25 (2004), no. 6, 863–871. MR 2079903, DOI 10.1016/j.ejc.2003.06.005
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR 543793
- G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451. MR 18401, DOI 10.1090/S0002-9947-1946-0018401-4
- Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
- Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
- O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979), no. 3, 211–236. MR 534939, DOI 10.1016/0012-365X(79)90077-3
- O. V. Borodin, A. N. Glebov, M. Montassier, and A. Raspaud, Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. Combin. Theory Ser. B 99 (2009), no. 4, 668–673. MR 2518199, DOI 10.1016/j.jctb.2008.11.001
- Nathan Chenette, Luke Postle, Noah Streib, Robin Thomas, and Carl Yerger, Five-coloring graphs on the Klein bottle, J. Combin. Theory Ser. B 102 (2012), no. 5, 1067–1098. MR 2959391, DOI 10.1016/j.jctb.2012.05.001
- Vincent Cohen-Addad, Michael Hebdige, Daniel Král’, Zhentao Li, and Esteban Salgado, Steinberg’s conjecture is false, J. Combin. Theory Ser. B 122 (2017), 452–456. MR 3575214, DOI 10.1016/j.jctb.2016.07.006
- Alice M. Dean and Joan P. Hutchinson, List-coloring graphs on surfaces with varying list-sizes, Electron. J. Combin. 19 (2012), no. 4, Paper 50, 16. MR 3007185, DOI 10.37236/2487
- Matt DeVos, Ken-ichi Kawarabayashi, and Bojan Mohar, Locally planar graphs are 5-choosable, J. Combin. Theory Ser. B 98 (2008), no. 6, 1215–1232. MR 2462315, DOI 10.1016/j.jctb.2008.01.003
- Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811, DOI 10.1007/978-3-642-14279-6
- G. A. Dirac, Map-colour theorems, Canad. J. Math. 4 (1952), 480–490. MR 50869, DOI 10.4153/cjm-1952-043-9
- G. A. Dirac, The colouring of maps, J. London Math. Soc. 28 (1953), 476–480. MR 56904, DOI 10.1112/jlms/s1-28.4.476
- Zdeněk Dvořák, 3-choosability of planar graphs with $(\leq 4)$-cycles far apart, J. Combin. Theory Ser. B 104 (2014), 28–59. MR 3132743, DOI 10.1016/j.jctb.2013.10.004
- Zdeněk Dvořák and Ken-ichi Kawarabayashi, Choosability of planar graphs of girth $5$, arXiv:1109.2976v1.
- Zdeněk Dvořák and Ken-ichi Kawarabayashi, List-coloring embedded graphs, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2012, pp. 1004–1012. MR 3202964
- Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces, Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New York, NY (2009), 120–129.
- Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Testing first-order properties for subclasses of sparse graphs, J. ACM 60 (2013), no. 5, Art. 36, 24. MR 3124685, DOI 10.1145/2499483
- Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces III. Graphs of girth five, arXiv:1402.4710.
- Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies, arXiv:0911.0885.
- Zdeněk Dvořák, Daniel Král’, and Robin Thomas, Three-coloring triangle-free graphs on surfaces VI. $3$-colorability of quadrangulations, arXiv:1509.01013.
- Zdeněk Dvořák, Bernard Lidický, and Bojan Mohar, 5-choosability of graphs with crossings far apart, J. Combin. Theory Ser. B 123 (2017), 54–96. MR 3597095, DOI 10.1016/j.jctb.2016.11.004
- Zdeněk Dvořák, Bernard Lidický, Bojan Mohar, and Luke Postle, 5-list-coloring planar graphs with distant precolored vertices, J. Combin. Theory Ser. B 122 (2017), 311–352. MR 3575207, DOI 10.1016/j.jctb.2016.06.006
- David Eppstein, Subgraph isomorphism in planar graphs and related problems, J. Graph Algorithms Appl. 3 (1999), no. 3, 27. MR 1750082, DOI 10.7155/jgaa.00014
- Paul Erdős, Arthur L. Rubin, and Herbert Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979) Congress. Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980, pp. 125–157. MR 593902
- P. Franklin, A Six Color Problem, J. Math. Phys. 13 (1934), 363–379.
- 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
- T. Gallai, Kritische Graphen. II, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373–395 (1964) (German, with Russian summary). MR 188100
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
- 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
- Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 (1958/59), 109–120 (German). MR 116320
- Ivan Havel, O zbarvitelnosti rovinných grafů třemi barvami, Mathematics (Geometry and Graph Theory), Univ. Karlova, Prague (1970), 89–91.
- Joan P. Hutchinson, On list-coloring extendable outerplanar graphs, Ars Math. Contemp. 5 (2012), no. 1, 171–184. MR 2880673, DOI 10.26493/1855-3974.179.189
- T. R. Jensen and B. Toft, Graph Coloring Problems, J. Wiley & Sons, New York, Chichester, Brisbane, Toronto, Singapore 1995.
- Ken-ichi Kawarabayashi, Daniel Kráľ, Jan Kynčl, and Bernard Lidický, 6-critical graphs on the Klein bottle, SIAM J. Discrete Math. 23 (2008/09), no. 1, 372–383. MR 2476836, DOI 10.1137/070706835
- Ken-ichi Kawarabayashi and Bojan Mohar, List-color-critical graphs on a fixed surface, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 1156–1165. MR 2807558
- Ken-ichi Kawarabayashi and Carsten Thomassen, From the plane to higher surfaces, J. Combin. Theory Ser. B 102 (2012), no. 4, 852–868. MR 2927410, DOI 10.1016/j.jctb.2012.03.001
- Tom Kelly and Luke Postle, Exponentially many 4-list colorings of triangle-free graphs on surfaces, J. Graph Theory 87 (2018), no. 2, 230–238. MR 3742180, DOI 10.1002/jgt.22153
- Bojan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. MR 1844449
- Luke Jamison Postle, 5-list-coloring graphs on surfaces, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–Georgia Institute of Technology. MR 3152411
- Luke Postle, 3 list coloring graphs of girth at least five on surfaces, arXiv:1710.06898v1.
- Luke Postle and Robin Thomas, Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs, J. Combin. Theory Ser. B 111 (2015), 234–241. MR 3315607, DOI 10.1016/j.jctb.2014.08.003
- Luke Postle and Robin Thomas, Five-list-coloring graphs on surfaces II. A linear bound for critical graphs in a disk, J. Combin. Theory Ser. B 119 (2016), 42–65. MR 3486337, DOI 10.1016/j.jctb.2015.12.005
- Luke Postle and Robin Thomas, Five-list-coloring graphs on surfaces III. One list of size one and one list of size two, J. Combin. Theory Ser. B 128 (2018), 1–16. MR 3725183, DOI 10.1016/j.jctb.2017.06.004
- Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438–445. MR 228378, DOI 10.1073/pnas.60.2.438
- Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44. MR 1441258, DOI 10.1006/jctb.1997.1750
- 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
- Carsten Thomassen, Five-coloring graphs on the torus, J. Combin. Theory Ser. B 62 (1994), no. 1, 11–33. MR 1290628, DOI 10.1006/jctb.1994.1052
- Carsten Thomassen, Every planar graph is $5$-choosable, J. Combin. Theory Ser. B 62 (1994), no. 1, 180–181. MR 1290638, DOI 10.1006/jctb.1994.1062
- Carsten Thomassen, Grötzsch’s $3$-color theorem and its counterparts for the torus and the projective plane, J. Combin. Theory Ser. B 62 (1994), no. 2, 268–279. MR 1305053, DOI 10.1006/jctb.1994.1069
- Carsten Thomassen, $3$-list-coloring planar graphs of girth $5$, J. Combin. Theory Ser. B 64 (1995), no. 1, 101–107. MR 1328294, DOI 10.1006/jctb.1995.1027
- 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
- Carsten Thomassen, A short list color proof of Grötzsch’s theorem, J. Combin. Theory Ser. B 88 (2003), no. 1, 189–192. MR 1974149, DOI 10.1016/S0095-8956(03)00029-7
- Carsten Thomassen, The chromatic number of a graph of girth 5 on a fixed surface, J. Combin. Theory Ser. B 87 (2003), no. 1, 38–71. Dedicated to Crispin St. J. A. Nash-Williams. MR 1967881, DOI 10.1016/S0095-8956(02)00027-8
- Carsten Thomassen, The number of $k$-colorings of a graph on a fixed surface, Discrete Math. 306 (2006), no. 23, 3145–3153. MR 2273145, DOI 10.1016/j.disc.2005.04.027
- Carsten Thomassen, Exponentially many 5-list-colorings of planar graphs, J. Combin. Theory Ser. B 97 (2007), no. 4, 571–583. MR 2325797, DOI 10.1016/j.jctb.2006.09.002
- Carsten Thomassen, Many 3-colorings of triangle-free planar graphs, J. Combin. Theory Ser. B 97 (2007), no. 3, 334–349. MR 2305887, DOI 10.1016/j.jctb.2006.06.005
- Margit Voigt, List colourings of planar graphs, Discrete Math. 120 (1993), no. 1-3, 215–219. MR 1235909, DOI 10.1016/0012-365X(93)90579-I
- Carl Roger Yerger Jr, Color-critical graphs on surfaces, ProQuest LLC, Ann Arbor, MI, 2010. Thesis (Ph.D.)–Georgia Institute of Technology. MR 2941743
Additional Information
- Luke Postle
- Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 898019
- Email: lpostle@uwaterloo.ca
- Robin Thomas
- Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332-0160
- MR Author ID: 217850
- Email: thomas@math.gatech.edu
- Received by editor(s): June 28, 2017
- Received by editor(s) in revised form: April 11, 2018
- Published electronically: December 4, 2018
- Additional Notes: The first author was partially supported by NSERC under Discovery Grant No. 2014-06162, the Ontario Early Researcher Awards program and the Canada Research Chairs program.
The second author was partially supported by NSF under Grant No. DMS-1202640. - © Copyright 2018 by the authors under Creative Commons Attribution 3.0 License (CC BY 3.0)
- Journal: Trans. Amer. Math. Soc. Ser. B 5 (2018), 167-221
- MSC (2010): Primary 05C10, 05C15
- DOI: https://doi.org/10.1090/btran/26
- MathSciNet review: 3882883