A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1567,
author = {J\'ulius Czap and Stanislav Jendro\v l and Franti\v sek Kardo\v s},
title = {On the strong parity chromatic number},
journal = {Discussiones Mathematicae Graph Theory},
volume = {31},
year = {2011},
pages = {587-600},
zbl = {1229.05101},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1567}
}
Július Czap; Stanislav Jendroľ; František Kardoš. On the strong parity chromatic number. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 587-600. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1567/
[000] [1] 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. | Zbl 0331.05106
[001] [2] O.V. Borodin, Solution of Ringel's problems on vertex-free coloring of plane graphs and coloring of 1-planar graphs,, Met. Diskret. Anal. 41 (1984) 12-26 (in Russian). | Zbl 0565.05027
[002] [3] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507-521, doi: 10.1002/jgt.3190190406. | Zbl 0826.05027
[003] [4] O.V. Borodin, D.P. Sanders and Y. Zhao, On cyclic coloring and their generalizations, Discrete Math. 203 (1999) 23-40, doi: 10.1016/S0012-365X(99)00018-7. | Zbl 0929.05027
[004] [5] P. Borowiecki, K. Budajová, S. Jendroľ and S. Krajci, Parity vertex colouring of graphs, Discuss. Math. Graph Theory 31 (2011) 183-195, doi: 10.7151/dmgt.1537. | Zbl 1284.05091
[005] [6] D.P. Bunde, K. Milans, D.B. West and H. Wu, Parity and strong parity edge-coloring of graphs, Congressus Numerantium 187 (2007) 193-213. | Zbl 1135.05020
[006] [7] 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. | Zbl 1193.05065
[007] [8] J. Czap, S. Jendroľ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemporanea 4 (2011) 255-269.
[008] [9] 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. | Zbl 1222.05051
[009] [10] H. Enomoto and M. Horná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. | Zbl 1190.05052
[010] [11] H. Enomoto, M. Hornák and S. Jendroľ, Cyclic chromatic number of 3-connected plane graphs, SIAM J. Discrete Math. 14 (2001) 121-137, doi: 10.1137/S0895480198346150. | Zbl 0960.05048
[011] [12] M. Hornák and J. Zl' amalová, Another step towards proving a conjecture by Plummer and Toft, Discrete Math. 310 (2010) 442-452, doi: 10.1016/j.disc.2009.03.016.
[012] [13] T. Kaiser, O. Ruck'y, M. Stehl'ik and R. Skrekovski, Strong parity vertex coloring of plane graphs, IMFM, Preprint series 49 (2011), 1144.
[013] [14] O. Ore, The Four-color Problem, (Academic Press, New York, 1967) | Zbl 0149.21101
[014] [15] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427-439, doi: 10.1007/BF01215922. | Zbl 0902.05017
[015] [16] D.P. Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory (B) 83 (2001) 102-111. | Zbl 1027.05044