  Restricted star colouring is a variant of star colouring introduced to design
heuristic algorithms to estimate sparse Hessian matrices. For $k\in\mathbb{N}$,
a $k$-restricted star colouring ($k$-rs colouring) of a graph $G$ is a function
$f:V(G)\to{0,1,\dots,k-1}$ such that (i)$f(x)\neq f(y)$ for every edge $xy$ of
G, and (ii) there is no bicoloured 3-vertex path ($P_3$) in $G$ with the higher
colour on its middle vertex. We show that for $k\geq 3$, it is NP-complete to
test whether a given planar bipartite graph of maximum degree $k$ and
arbitrarily large girth admits a $k$-rs colouring, and thereby answer a problem
posed by Shalu and Sandhya (Graphs and Combinatorics, 2016). In addition, it is
NP-complete to test whether a 3-star colourable graph admits a 3-rs colouring.
We also prove that for all $\epsilon > 0$, the optimization problem of
restricted star colouring a 2-degenerate bipartite graph with the minimum
number of colours is NP-hard to approximate within $n^{(1/3)-\epsilon}$. On the
positive side, we design (i) a linear-time algorithm to test 3-rs colourability
of trees, and (ii) an $O(n^3)$-time algorithm to test 3-rs colourability of
chordal graphs.
