# 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

## Access Full Article

top## Abstract

top## How to cite

topJú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] K. Appel and W. Haken, Every planar map is four colorable, Contemporary Mathematics 98 (American Mathematical Society, 1989). Zbl0681.05027
- [2] K. Budajová, S. Jendrol and S. Krajci, Parity vertex colouring of graphs, manuscript (2007). Zbl1284.05091
- [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] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & HALL/CRC, Boca Raton, 2005).
- [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] 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] 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] S. Jendrol, Rainbowness of cubic plane graphs, Discrete Math. 306 (2006) 3321-3326, doi: 10.1016/j.disc.2006.06.012. Zbl1109.05044
- [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] H. Lebesgue, Quelques consequences simple de la formula d'Euler, J. de Math. Pures Appl. 9 (1940) 27-43. Zbl0024.28701
- [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] 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] 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] N. Rampersad, A note on non-repetitive colourings of planar graphs, manuscript (2003).
- [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] 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