Geodesic
Colouring vertices of plane graphs under restrictions given by faces
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 521-543

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2009_29_3_a5,
     author = {Czap, J\'ulius and Jendrol', Stanislav},
     title = {Colouring vertices of plane graphs under restrictions given by faces},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {521--543},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a5/}
}
TY  - JOUR
AU  - Czap, Július
AU  - Jendrol', Stanislav
TI  - Colouring vertices of plane graphs under restrictions given by faces
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 521
EP  - 543
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a5/
LA  - en
ID  - DMGT_2009_29_3_a5
ER  - 
%0 Journal Article
%A Czap, Július
%A Jendrol', Stanislav
%T Colouring vertices of plane graphs under restrictions given by faces
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 521-543
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a5/
%G en
%F DMGT_2009_29_3_a5
Czap, Július; Jendrol', Stanislav. Colouring vertices of plane graphs under restrictions given by faces. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 521-543. http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a5/