ArticleOriginal scientific text
Title
Colouring vertices of plane graphs under restrictions given by faces
Authors 1, 1
Affiliations
- Institute of Mathematics, P.J. Šafárik University, Jesenná 5, SK-04001 Košice, Slovakia
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.
Keywords
vertex colouring, plane graph, weak parity vertex colouring, strong parity vertex colouring, proper colouring, Lebesgue theorem
Bibliography
- K. Appel and W. Haken, Every planar map is four colorable, Contemporary Mathematics 98 (American Mathematical Society, 1989).
- K. Budajová, S. Jendrol and S. Krajci, Parity vertex colouring of graphs, manuscript (2007).
- D.P. Bunde, K. Milans, D.B. West and H. Wu, Parity and strong parity edge-coloring of graphs, manuscript (2006).
- G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & HALL/CRC, Boca Raton, 2005).
- 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.
- 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
- 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).
- S. Jendrol, Rainbowness of cubic plane graphs, Discrete Math. 306 (2006) 3321-3326, doi: 10.1016/j.disc.2006.06.012.
- 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.
- H. Lebesgue, Quelques consequences simple de la formula d'Euler, J. de Math. Pures Appl. 9 (1940) 27-43.
- 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.
- O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: W.T. Tutte, Recent Progress in Combinatorics Academic Press (1969) 287-293.
- M.D. Plummer and B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507-515, doi: 10.1002/jgt.3190110407.
- N. Rampersad, A note on non-repetitive colourings of planar graphs, manuscript (2003).
- 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.
- 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.
Pages:
521-543
Main language of publication
English
Received
2008-03-28
Accepted
2008-08-19
Published
2009
DOI: 10.7151/dmgt.1462
Exact and natural sciences