×

Cyclic 4-colorings of graphs on surfaces. (English) Zbl 1342.05048

Summary: To attack the four color problem, P. G. Tait [“Remaks on the colouring of maps”, Proc. R. Soc. Lond. 10, 729 (1880)] gave a necessary and sufficient condition for plane triangulations to have a proper 4-vertex-coloring: a plane triangulation \(G\) has a proper 4-vertex-coloring if and only if the dual of \(G\) has a proper 3-edge-coloring. A cyclic coloring of a map \(G\) on a surface \(F^{2}\) is a vertex-coloring of \(G\) such that any two vertices \(x\) and \(y\) receive different colors if \(x\) and \(y\) are incident with a common face of \(G\). In this article, we extend the result by Tait to two directions, that is, considering maps on a nonspherical surface and cyclic 4-colorings.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, Polychromatic colorings of plane graphs, Discrete Comput Geom 42 pp 421– (2009) · Zbl 1214.05021 · doi:10.1007/s00454-009-9171-5
[2] Appel, Every planar map is four colorable, Bull Amer Math Soc 82 pp 449– (1976) · Zbl 0331.05106 · doi:10.1090/S0002-9904-1976-14122-5
[3] Berman, Full 4-colorings of 4-regular maps, J Graph Theory 3 pp 291– (1979) · Zbl 0414.05020 · doi:10.1002/jgt.3190030312
[4] Borodin, Solution of Ringel’s problems on vertex-face coloring of plane graphs and coloring of 1-planar graphs, Met Diskret Anal 41 pp 12– (1984) · Zbl 0565.05027
[5] Borodin, A new proof of the 6 color theorem, J Graph Theory 19 pp 507– (1995) · Zbl 0826.05027 · doi:10.1002/jgt.3190190406
[6] Borodin, Cyclic coloring of plane graphs, Discrete Math 100 pp 281– (1992) · Zbl 0765.05044 · doi:10.1016/0012-365X(92)90647-X
[7] Devos, Coloring-flow duality of embedded graphs, Trans Amer Math Soc 357 pp 3993– (2005) · Zbl 1065.05034 · doi:10.1090/S0002-9947-04-03544-5
[8] Enomoto, Cyclic chromatic number of 3-connected plane graphs, SIAM J Discrete Math 14 pp 121– (2001) · Zbl 0960.05048 · doi:10.1137/S0895480198346150
[9] L. Goddyn Wide embedded graphs behave chromatically like plane or projective plane graphs 2005 160 162
[10] Grünbaum, Recent Progress in Combinatorics pp 343– (1969)
[11] A. Hoffmann-Ostenhof Mosaics, even triangulations and quadrangulations of the sphere preprint
[12] Horev, Polychromatic 4-coloring of cubic bipartite plane graphs, Discrete Math 312 pp 715– (2012) · Zbl 1316.05044 · doi:10.1016/j.disc.2011.11.016
[13] Horňák, Another step towards proving a conjecture of Plummer and Toft, Discrete Math 310 pp 442– (2010) · Zbl 1185.05060 · doi:10.1016/j.disc.2009.03.016
[14] Karp, Complexity of computer computations pp 85– (1972) · doi:10.1007/978-1-4684-2001-2_9
[15] Kochol, Polyhedral embeddings of snarks in orientable surfaces, Proc Amer Math Soc 137 pp 1613– (2009) · Zbl 1197.05052 · doi:10.1090/S0002-9939-08-09698-6
[16] Mohar, Graphs on Surfaces (2001)
[17] Ore, Recent Progress in Combinatorics pp 287– (1969)
[18] Robertson, The four color theorem, J Combin Theory Ser B 70 pp 2– (1997) · Zbl 0883.05056 · doi:10.1006/jctb.1997.1750
[19] Sanders, A new bound on the cyclic chromatic number, J Combin Theory Ser B 83 pp 102– (2001) · Zbl 1027.05044 · doi:10.1006/jctb.2001.2046
[20] Stockmeyer, Planar 3-colorability is polynomial complete, SIGACT News 5 pp 19– (1973) · doi:10.1145/1008293.1008294
[21] Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J Discrete Math 24 pp 1527– (2010) · Zbl 1221.05099 · doi:10.1137/090746835
[22] Tait, Remarks on the colouring of maps, Proc Roya Soc London 10 pp 729– (1880)
[23] Thomassen, Five-coloring maps on surfaces, J Combin Theory Ser B 59 pp 89– (1993) · Zbl 0794.05026 · doi:10.1006/jctb.1993.1057
[24] Zhang, Circuit Double Cover of Graphs (2012) · Zbl 1250.05006 · doi:10.1017/CBO9780511863158
[25] Zhu, Circular chromatic number: A survey, Discrete Math 229 pp 371– (2001) · Zbl 0973.05030 · doi:10.1016/S0012-365X(00)00217-X
[26] Zhu, Topics in Discrete Mathematics pp 497– (2006) · doi:10.1007/3-540-33700-8_25
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.