  A vertex colouring is called a \emph{parity vertex colouring} if every path
in $G$ contains an odd number of occurrences of some colour. Let $\chi_{p}(G)$
be the minimal number of colours in a parity vertex colouring of $G$. We show
that $\chi_{p}(B^*) \ge \sqrt{d} + \frac{1}{4} \log_2(d) - \frac{1}{2}$ where
$B^*$ is a subdivision of the complete binary tree $B_d$. This improves the
previously known bound $\chi_{p}(B^*) \ge \sqrt{d}$ and enhances the techniques
used for proving lower bounds. We use this result to show that $\chi_{p}(T) >
\sqrt[3]{\log{n}}$ where $T$ is any binary tree with $n$ vertices. These lower
bounds are also lower bounds for the conflict-free colouring. We also prove
that $\chi_{p}(G)$ is not monotone with respect to minors and determine its
value for cycles. Furthermore, we study complexity of computing the parity
vertex chromatic number $\chi_{p}(G)$. We show that checking whether a vertex
colouring is a parity vertex colouring is coNP-complete. Then we use
Courcelle's theorem to prove that the problem of checking whether $\chi_{p}(G)
\le k$ is fixed-parameter tractable with respect $k$ and the treewidth of $G$.
