A Survey on the Cyclic Coloring and its Relaxations

Czap, Július ; Horňák, Mirko ; Jendroľ, Stanislav

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 5-38.

Résumé

A cyclic coloring of a plane graph is a vertex coloring such that any two vertices incident with the same face receive distinct colors. This type of coloring was introduced more than fifty years ago, and a lot of research in chromatic graph theory was sparked by it. This paper is a survey on the state of the art concerning the cyclic coloring and relaxations of this graph invariant.

Détail

Keywords: plane graph, edge coloring, vertex coloring

Bibliographie

[1] O. Amini, L. Esperet and J. van den Heuvel, A unified approach to distance-two colouring of graphs on surfaces, Combinatorica 33 (2013) 253–296. doi: 10.1007/s00493-013-2573-2

[2] V. Andova, B. Lidický, B. Lužar and R. Škrekovski, On facial unique-maximum (edge-) coloring, Discrete Appl. Math. 237 (2018) 26–32. doi: 10.1016/j.dam.2017.11.024

[3] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712. doi: 10.1090/s0002-9904-1976-14122-5

[4] K. Appel and W. Haken, Every planar map is four colorable, Part I: Discharging, Illinois J. Math. 21 (1977) 429–490. doi: 10.1215/ijm/1256049011

[5] K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Part II: Reducibility, Illinois J. Math. 21 (1977) 491–567. doi: 10.1215/ijm/1256049012

[6] J. Azarija, R. Erman, D. Kráľ, M. Krnc and L. Stacho, Cyclic colorings of plane graphs with independent faces, European J. Combin. 33 (2012) 294–301. doi: 10.1016/j.ejc.2011.09.011

[7] T. Bálint and J. Czap, Facial parity 9-edge-coloring of outerplane graphs, Graphs Combin. 31 (2015) 1177–1187. doi: 10.1007/s00373-014-1472-7

[8] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507–521. doi: 10.1002/jgt.3190190406

[9] O.V. Borodin, Cyclic coloring of plane graphs, Discrete Math. 100 (1992) 281–289. doi: 10.1016/0012-365x(92)90647-x

[10] O.V. Borodin, Cyclic degree and cyclic coloring of 3-polytopes, J. Graph Theory 23 (1996) 225–231. doi: 10.1002/(sici)1097-0118(199611)23:3(225::aid-jgt2)3.0.co;2-u

[11] O.V. Borodin, Solution of Ringel's problems on vertex-face coloring of plane graphs and coloring of 1- planar graphs, Met. Diskret. Anal. 41 (1984) 12–26.

[12] O.V. Borodin, H.J. Broersma, A. Glebov and J. van den Heuvel, A new upper bound on the cyclic chromatic number, J. Graph Theory 54 (2007) 58–72. doi: 10.1002/jgt.20193

[13] O.V. Borodin and A.O. Ivanova, List 2- facial 5- colorability of plane graphs with girth at least 12, Discrete Math. 312 (2012) 306–314. doi: 10.1016/j.disc.2011.09.018

[14] O.V. Borodin and D.R. Woodall, Cyclic colorings of 3-polytopes with large maximum face size, SIAM J. Discrete Math. 15 (2002) 143–154. doi: 10.1137/s089548019630248x

[15] O.V. Borodin, D.P. Sanders and Y. Zhao, On cyclic colorings and their generalizations, Discrete Math. 203 (1999) 23–40. doi: 10.1016/s0012-365x(99)00018-7

[16] Y. Bu and W. Wang, Some sufficient conditions for a planar graph of maximum degree six to be class 1, Discrete Math. 306 (2006) 1440–1445. doi: 10.1016/j.disc.2006.03.032

[17] J. Czap, Facial parity edge coloring of outerplane graphs, Ars Math. Contemp. 5 (2012) 285–289. doi: 10.26493/1855-3974.228.ee8

[18] J. Czap, Facial rainbow edge-coloring of simple 3-connected plane graphs, Opuscula Math. 40 (2020) 475–482. doi: 10.7494/OpMath.2020.40.4.475

[19] J. Czap, Parity vertex coloring of outerplane graphs, Discrete Math. 311 (2011) 2570–2573. doi: 10.1016/j.disc.2011.06.009

[20] J. Czap and S. Jendroľ, Colouring vertices of plane graphs under restrictions given by faces, Discuss. Math. Graph Theory 29 (2009) 521–543. doi: 10.7151/dmgt.1462

[21] J. Czap, S. Jendroľ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemp. 4 (2011) 255–269. doi: 10.26493/1855-3974.129.be3

[22] J. Czap, S. Jendroľ and F. Kardoš, On the strong parity chromatic number, Discuss. Math. Graph Theory 31 (2011) 587–600. doi: 10.7151/dmgt.1567

[23] J. Czap, S. Jendroľ, F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudographs, Discrete Math. 312 (2012) 2735–2740. doi: 10.1016/j.disc.2012.03.036

[24] J. Czap, S. Jendroľ and M. Voigt, Parity vertex colouring of plane graphs, Discrete Math. 311 (2011) 512–520. doi: 10.1016/j.disc.2010.12.008

[25] J. Czap and Zs. Tuza, Decompositions of plane graphs under parity constrains given by faces, Discuss. Math. Graph Theory 33 (2013) 521–530. doi: 10.7151/dmgt.1690

[26] Z. Dvořák, M. Hebdige, F. Hlásek, D. Kráľ and J.A. Noel: Cyclic coloring of plane graphs with maximum face size 16 and 17. arXiv:1603.06722.

[27] Z. Dvořák, R. Škrekovski and M. Tancer, List-coloring squares of sparse subcubic graphs, SIAM J. Discrete Math. 22 (2008) 139–159. doi: 10.1137/050634049

[28] H. Enomoto and M. Horňák, A general upper bound for the cyclic chromatic number of 3- connected plane graphs, J. Graph Theory 62 (2009) 1–25. doi: 10.1002/jgt.20383

[29] H. Enomoto, M. Horňák and S. Jendroľ, Cyclic chromatic number of 3- connected plane graphs, SIAM J. Discrete Math. 14 (2001) 121–137. doi: 10.1137/s0895480198346150

[30] I. Fabrici and F. Göring, Unique-maximum coloring of plane graphs, Discuss. Math. Graph Theory 36 (2016) 95–102. doi: 10.7151/dmgt.1846

[31] I. Fabrici, S. Jendroľ and M. Vrbjarová, Unique-maximum edge-colouring of plane graphs with respect to faces, Discrete Appl. Math. 185 (2015) 239–243. doi: 10.1016/j.dam.2014.12.002

[32] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001).

[33] J.L. Gross and T.W. Tucker, Topological Graph Theory (Dover Publications, 2001).

[34] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Universität, Halle-Wittenberg, Math.-Nat. Reihe 8 (1959) 109–120.

[35] F. Havet, J.-S. Sereni and R. Škrekovski, 3- facial coloring of plane graphs, SIAM J. Discrete Math. 22 (2008) 231–247. doi: 10.1137/060664124

[36] F. Havet, D. Kráľ, J.-S. Sereni and R. Škrekovski, Facial colorings using Hall's theorem, European J. Combin. 31 (2010) 1001–1019. doi: 10.1016/j.ejc.2009.10.003

[37] M. Hebdige and D. Kráľ, Third case of the cyclic coloring conjecture, SIAM J. Discrete Math. 30 (2016) 525–548. doi: 10.1137/15m1019490

[38] M. Horňák and S. Jendroľ, On a conjecture by Plummer and Toft, J. Graph Theory 30 (1999) 177–189. doi: 10.1002/(sici)1097-0118(199903)30:3(177::aid-jgt3)3.0.co;2-k

[39] M. Horňák and S. Jendroľ, On vertex types and cyclic colourings of 3-connected plane graphs, Discrete Math. 212 (2000) 101–109. doi: 10.1016/s0012-365x(99)00212-5

[40] M. Horňák and S. Jendroľ, Unavoidable sets of face types for planar maps, Discuss. Math. Graph Theory 16 (1996) 123–141. doi: 10.7151/dmgt.1028

[41] M. Horňák and J. Zlámalová, Another step towards proving a conjecture by Plummer and Toft, Discrete Math. 310 (2010) 442–452. doi: 10.1016/j.disc.2009.03.016

[42] D. Huang and W. Wang, Planar graphs of maximum degree six without 7-cycles are class one, Electron. J. Combin. 19(3) (2012) #P17. doi: 10.37236/2589

[43] S. Jendroľ, Facial rainbow edge-coloring of plane graphs, Graphs Combin. 34 (2018) 669–676. doi: 10.1007/s00373-018-1904-x

[44] S. Jendroľ and L. Kekeňáková, Facial rainbow coloring of plane graphs, Discuss. Math. Graph Theory 39 (2019) 889–897. doi: 10.7151/dmgt.2047

[45] S. Jendroľ and L. Kekeňáková, Facial rainbow colorings of trees, Australas. J. Combin. 69 (2017) 358–367.

[46] S. Jendroľ and R. Soták, On the cyclic coloring conjecture, Discrete Math. (2020) accepted.

[47] T. Kaiser, O. Rucký, M. Stehlík and R. Škrekovski, Strong parity vertex coloring of plane graphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 143–158.

[48] D. Kráľ, T. Madaras and R. Škrekovski, Cyclic, diagonal and facial colorings, European J. Combin. 26 (2005) 473–490. doi: 10.1016/j.ejc.2004.01.016

[49] D. Kráľ, T. Madaras and R. Škrekovski, Cyclic, diagonal and facial colorings—a missing case, European J. Combin. 28 (2007) 1637–1639. doi: 10.1016/j.ejc.2006.07.005

[50] M. Kriesell, Contractions, cycle double covers, and cyclic colorings in locally connected graphs, J. Combin. Theory Ser. B 96 (2006) 881–900. doi: 10.1016/j.jctb.2006.02.009

[51] B. Lidický, K. Messerschmidt and R. Škrekovski, A counterexample to a conjecture on facial unique-maximal colorings, Discrete Appl. Math. 237 (2018) 123–125. doi: 10.1016/j.dam.2017.11.037

[52] B. Lidický, K. Messerschmidt and R. Škrekovski, Facial unique-maximum colorings of plane graphs with restriction on big vertices, Discrete Appl. Math. 242 (2019) 2612–2617. doi: 10.1016/j.disc.2019.05.029

[53] B. Lužar, M. Mockovčiaková, R. Soták, R. Škrekovski and P. Šugerek, ℓ-facial edge colorings of graphs, Discrete Appl. Math. 181 (2015) 193–200. doi: 10.1016/j.dam.2014.10.009

[54] B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013) 2218–2222. doi: 10.1016/j.disc.2013.05.022

[55] B. Mohar and C. Thomassen, Graphs on Surfaces (The Johns Hopkins University Press, 2001).

[56] M. Montassier and A. Raspaud, A note on 2-facial coloring of plane graphs, Inform. Process. Lett. 98 (2006) 235–241. doi: 10.1016/j.ipl.2006.02.013

[57] W.-P. Ni, Edge colorings of planar graphs with Δ = 6 without short cycles contain chords, J. Nanjing Norm. Univ. Nat. Sci. Ed. 34 (2011) 19–24.

[58] W.-P. Ni, Edge colorings of planar graphs without adjacent special cycles, Ars Combin. 105 (2012) 247–256.

[59] W.-P. Ni and J. Wu, Edge coloring of planar graphs which any two short cycles are adjacent at most once, Theoret. Comput. Sci. 516 (2014) 133–138. doi: 10.1016/j.tcs.2013.11.011

[60] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics (Proceedings of the Third Waterloo Conference on Combinatorics), (Academic Press, 1969) 287–293.

[61] M.D. Plummer and B. Toft, Cyclic coloration of 3- polytopes, J. Graph Theory 11 (1987) 507–515. doi: 10.1002/jgt.3190110407

[62] N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1999) 2–44. doi: 10.1006/jctb.1997.1750

[63] D.P. Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory Ser. B 83 (2001) 102–111. doi: 10.1006/jctb.2001.2046

[64] D.P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B 83 (2001) 201–212. doi: 10.1006/jctb.2001.2047

[65] C.E. Shannon, A theorem on coloring the lines of a network, J. Math. Phys. 28 (1949) 148–152. doi: 10.1002/sapm1949281148

[66] K. Štorgel, Improved bounds for some facially constrained colorings, Discuss. Math. Graph Theory, in press. doi: 10.7151/dmgt.2357

[67] P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880) 729.

[68] C. Thomassen, The square of a planar cubic graph is 7- colorable, J. Combin. Theory Ser. B 128 (2018) 192–218. doi: 10.1016/j.jctb.2017.08.010

[69] V.G. Vizing, Critical graphs with a given chromatic class, Met. Diskret. Anal. 5 (1965) 9–17.

[70] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25–30.

[71] W. Wang and Y. Chen, A sufficient condition for a planar graph to be class 1, Theoret. Comput. Sci. 385 (2007) 71–77. doi: 10.1016/j.tcs.2007.05.032

[72] W. Wang, S. Finbow and P. Wang, An improved bound on parity vertex colourings of outerplane graphs, Discrete Math. 312 (2012) 2782–2787. doi: 10.1016/j.disc.2012.04.009

[73] Y. Wang and L. Xu, A sufficient condition for a plane graph with maximum degree 6 to be class 1, Discrete Appl. Math. 161 (2013) 307–310. doi: 10.1016/j.dam.2012.08.011

[74] A. Wendland, Coloring of plane graphs with unique maximal colors on faces, J. Graph Theory 83 (2016) 359–371. doi: 10.1002/jgt.22002

[75] J. Wu and L. Xue, Edge colorings of planar graphs without 5- cycles with two chords, Theoret. Comput. Sci. 518 (2014) 124–127. doi: 10.1016/j.tcs.2013.07.027

[76] L. Xue and J. Wu, Edge colorings of planar graphs without 6- cycles with two chords, Open J. Discrete Math. 3 (2013) 83–85. doi: 10.4236/ojdm.2013.32016

[77] W. Zhang and J. Wu, A note on the edge colorings of planar graphs without 7- cycles with three chords, Ars Combin. 138 (2018) 393–402.

[78] W. Zhang and J. Wu, Edge coloring of planar graphs without adjacent 7- cycles, Theoret. Comput. Sci. 739 (2018) 59–64. doi: 10.1016/j.tcs.2018.05.006

[79] W. Zhang and J. Wu, Edge colorings of planar graphs without 6- cycles with three chords, Bull. Malays. Math. Sci. Soc. 41 (2018) 1077–1084. doi: 10.1007/s40840-016-0376-5

[80] G. Zhou, A note on graphs of class I, Discrete Math. 263 (2003) 339–345. doi: 10.1016/s0012-365x(02)00793-8

[81] J. Zlámalová, A note on cyclic chromatic number, Discuss. Math. Graph Theory 30 (2010) 115–122. doi: 10.7151/dmgt.1481