# On the strong parity chromatic number

Július Czap; Stanislav Jendroľ; František Kardoš

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 587-600
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJúlius Czap, Stanislav Jendroľ, and František Kardoš. "On the strong parity chromatic number." Discussiones Mathematicae Graph Theory 31.3 (2011): 587-600. <http://eudml.org/doc/271057>.

@article{JúliusCzap2011,

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.},

author = {Július Czap, Stanislav Jendroľ, František Kardoš},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {plane graph; k-planar graph; vertex colouring; strong parity vertex colouring; -planar graph},

language = {eng},

number = {3},

pages = {587-600},

title = {On the strong parity chromatic number},

url = {http://eudml.org/doc/271057},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Július Czap

AU - Stanislav Jendroľ

AU - František Kardoš

TI - On the strong parity chromatic number

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 587

EP - 600

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

LA - eng

KW - plane graph; k-planar graph; vertex colouring; strong parity vertex colouring; -planar graph

UR - http://eudml.org/doc/271057

ER -

## References

top- [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. Zbl0331.05106
- [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). Zbl0565.05027
- [3] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507-521, doi: 10.1002/jgt.3190190406. Zbl0826.05027
- [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. Zbl0929.05027
- [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. Zbl1284.05091
- [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. Zbl1135.05020
- [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. Zbl1193.05065
- [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. Zbl1222.05051
- [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. Zbl1190.05052
- [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. Zbl0960.05048
- [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) Zbl0149.21101
- [15] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427-439, doi: 10.1007/BF01215922. Zbl0902.05017
- [16] D.P. Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory (B) 83 (2001) 102-111. Zbl1027.05044

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.