Geodesic
On the strong parity chromatic number
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 587-600.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2011_31_3_a12,
     author = {Czap, J\'ulius and Jendro\v{l}, Stanislav and Kardo\v{s}, Franti\v{s}ek},
     title = {On the strong parity chromatic number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {587--600},
     publisher = {mathdoc},
     volume = {31},
     number = {3},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a12/}
}
TY  - JOUR
AU  - Czap, Július
AU  - Jendroľ, Stanislav
AU  - Kardoš, František
TI  - On the strong parity chromatic number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 587
EP  - 600
VL  - 31
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a12/
LA  - en
ID  - DMGT_2011_31_3_a12
ER  - 
%0 Journal Article
%A Czap, Július
%A Jendroľ, Stanislav
%A Kardoš, František
%T On the strong parity chromatic number
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 587-600
%V 31
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a12/
%G en
%F DMGT_2011_31_3_a12
Czap, Július; Jendroľ, Stanislav; Kardoš, František. On the strong parity chromatic number. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 587-600. http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a12/

[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. Jendroľ 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. Jendroľ, 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. Jendroľ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemporanea 4 (2011) 255-269.

[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.

[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. Jendroľ, 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.

[16] D.P. Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory (B) 83 (2001) 102-111.