PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 3 | 587-600
Tytuł artykułu

On the strong parity chromatic number

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
31
Numer
3
Strony
587-600
Opis fizyczny
Daty
wydano
2011
otrzymano
2009-09-14
poprawiono
2011-05-23
zaakceptowano
2011-05-24
Twórcy
autor
  • Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice, Nĕmcovej 32, SK-04001 Košice, Slovakia
  • Institute of Mathematics, P.J. Šafárik University, Jesenná 5, SK-04001 Košice, Slovakia
  • Institute of Mathematics, P.J. Šafárik University, Jesenná 5, SK-04001 Košice, Slovakia
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1567
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.