Colouring vertices of plane graphs under restrictions given by faces

Július Czap; Stanislav Jendrol'

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 521-543
  • ISSN: 2083-5892

Abstract

top
We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other three kinds of colourings that require stronger restrictions.

How to cite

top

Július Czap, and Stanislav Jendrol'. "Colouring vertices of plane graphs under restrictions given by faces." Discussiones Mathematicae Graph Theory 29.3 (2009): 521-543. <http://eudml.org/doc/270834>.

@article{JúliusCzap2009,
abstract = {We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other three kinds of colourings that require stronger restrictions.},
author = {Július Czap, Stanislav Jendrol'},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex colouring; plane graph; weak parity vertex colouring; strong parity vertex colouring; proper colouring; Lebesgue theorem},
language = {eng},
number = {3},
pages = {521-543},
title = {Colouring vertices of plane graphs under restrictions given by faces},
url = {http://eudml.org/doc/270834},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Július Czap
AU - Stanislav Jendrol'
TI - Colouring vertices of plane graphs under restrictions given by faces
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 521
EP - 543
AB - We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other three kinds of colourings that require stronger restrictions.
LA - eng
KW - vertex colouring; plane graph; weak parity vertex colouring; strong parity vertex colouring; proper colouring; Lebesgue theorem
UR - http://eudml.org/doc/270834
ER -

References

top
  1. [1] K. Appel and W. Haken, Every planar map is four colorable, Contemporary Mathematics 98 (American Mathematical Society, 1989). Zbl0681.05027
  2. [2] K. Budajová, S. Jendrol and S. Krajci, Parity vertex colouring of graphs, manuscript (2007). Zbl1284.05091
  3. [3] D.P. Bunde, K. Milans, D.B. West and H. Wu, Parity and strong parity edge-coloring of graphs, manuscript (2006). Zbl1135.05020
  4. [4] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & HALL/CRC, Boca Raton, 2005). 
  5. [5] 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. Zbl0960.05048
  6. [6] M. Hornák and S. Jendrol, On a conjecture by Plummer and Toft, J. Graph Theory 30 (1999) 177-189, doi: 10.1002/(SICI)1097-0118(199903)30:3<177::AID-JGT3>3.0.CO;2-K 
  7. [7] M. Hornák and J. Zlámalová, Another step towards proving a conjecture by Plummer and Toft, IM Preprint, series A, No.11/2006 (2006). Zbl1185.05060
  8. [8] S. Jendrol, Rainbowness of cubic plane graphs, Discrete Math. 306 (2006) 3321-3326, doi: 10.1016/j.disc.2006.06.012. Zbl1109.05044
  9. [9] V. Jungic, D. Král and R. Skrekovski, Coloring of plane graphs with no rainbow faces, Combinatorica 26 (2006) 169-182, doi: 10.1007/s00493-006-0012-3. Zbl1174.05364
  10. [10] H. Lebesgue, Quelques consequences simple de la formula d'Euler, J. de Math. Pures Appl. 9 (1940) 27-43. Zbl0024.28701
  11. [11] M. Molloy and M.R. Salavatipour, A bound on the cyclic chromatic number of the square of a planar graph, J. Combin. Theory (B) 94 (2005) 189-213, doi: 10.1016/j.jctb.2004.12.005. Zbl1071.05036
  12. [12] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: W.T. Tutte, Recent Progress in Combinatorics Academic Press (1969) 287-293. Zbl0195.25701
  13. [13] M.D. Plummer and B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507-515, doi: 10.1002/jgt.3190110407. Zbl0655.05030
  14. [14] N. Rampersad, A note on non-repetitive colourings of planar graphs, manuscript (2003). 
  15. [15] R. Ramamurthi and D.B. West, Maximum face-constrained coloring of plane graphs, Discrete Math. 274 (2004) 233-240, doi: 10.1016/j.disc.2003.09.001. Zbl1032.05050
  16. [16] D.P. Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory (B) 83 (2001) 102-111, doi: 10.1006/jctb.2001.2046. 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.