Publications Repository - Gdańsk University of Technology

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 Xp(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 X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(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 ceil(log2(2+diam(T))) <= Xp(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.

Authors

• dr hab. inż. Piotr Borowiecki link open in new tab ,
• Kristina Budajova,
• Stanislav Jendrol,
• Stanislav Krajci