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

Abstract

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

How to cite

top

Jú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. [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. [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. [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. [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. [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. [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. [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. [8] J. Czap, S. Jendroľ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemporanea 4 (2011) 255-269. 
  9. [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. [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. [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. [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. [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. [14] O. Ore, The Four-color Problem, (Academic Press, New York, 1967) Zbl0149.21101
  15. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.