DMGT

Discussiones Mathematicae Graph Theory 31(3) (2011) 587-600
DOI: https://doi.org/10.7151/dmgt.1567

On the Strong Parity Chromatic Number

J'ulius Czap¹, Stanislav Jendrol ² and Frantisek Kardos ²

¹ Department of Applied Mathematics and Business Informatics
Faculty of Economics, Technical University of Košice
Nemcovej 32, SK-04001 Košice, Slovakia
² Institute of Mathematics, P.J. Safarik University
Jesenn'a 5, SK-04001 Košice, Slovakia

Abstract

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.

Keywords: plane graph, k-planar graph, vertex colouring, strong parity vertex colouring

2010 Mathematics Subject Classification: 05C15.

References

[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.
[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).
[3]	O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507--521, doi: 10.1002/jgt.3190190406.
[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.
[5]	P. Borowiecki, K. Budajová, S. Jendrol and S. Krajci, Parity vertex colouring of graphs, Discuss. Math. Graph Theory 31 (2011) 183--195, doi: 10.7151/dmgt.1537.
[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.
[7]	J. Czap and S. Jendrol, Colouring vertices of plane graphs under restrictions given by faces, Discuss. Math. Graph Theory 29 (2009) 521--543, doi: 10.7151/dmgt.1462.
[8]	J. Czap, S. Jendrol and F. Kardos, Facial parity edge colouring, Ars Math. Contemporanea 4 (2011) 255--269.
[9]	J. Czap, S. Jendrol and M. Voigt, Parity vertex colouring of plane graphs, Discrete Math. 311 (2011) 512--520, doi: 10.1016/j.disc.2010.12.008.
[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.
[11]	H. Enomoto, M. Hornák and S. Jendrol, Cyclic chromatic number of 3-connected plane graphs, SIAM J. Discrete Math. 14 (2001) 121--137, doi: 10.1137/S0895480198346150.
[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.
[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.
[14]	O. Ore, The Four-color Problem, (Academic Press, New York, 1967)
[15]	J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427--439, doi: 10.1007/BF01215922.

Received 14 September 2009
Revised 23 May 2011
Accepted 24 May 2011