Geodesic
Parity vertex colouring of graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 183-195

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

A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.
Keywords: parity colouring, graph colouring, vertex ranking, ordered colouring, tree, hypercube, Fibonacci number 
@article{DMGT_2011_31_1_a11,
     author = {Borowiecki, Piotr and Budajov\'a, Krist{\'\i}na and Jendrol', Stanislav and Krajci, Stanislav},
     title = {Parity vertex colouring of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {183--195},
     publisher = {mathdoc},
     volume = {31},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a11/}
}
TY  - JOUR
AU  - Borowiecki, Piotr
AU  - Budajová, Kristína
AU  - Jendrol', Stanislav
AU  - Krajci, Stanislav
TI  - Parity vertex colouring of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 183
EP  - 195
VL  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a11/
LA  - en
ID  - DMGT_2011_31_1_a11
ER  - 
%0 Journal Article
%A Borowiecki, Piotr
%A Budajová, Kristína
%A Jendrol', Stanislav
%A Krajci, Stanislav
%T Parity vertex colouring of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 183-195
%V 31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a11/
%G en
%F DMGT_2011_31_1_a11
Borowiecki, Piotr; Budajová, Kristína; Jendrol', Stanislav; Krajci, Stanislav. Parity vertex colouring of graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 183-195. http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a11/