and

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 χp(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) ≤ χp(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