  We study how the complexity of the graph colouring problems star colouring
and restricted star colouring vary with the maximum degree of the graph.
Restricted star colouring (in short, rs colouring) is a variant of star
colouring. For $k\in \mathbb{N}$, a $k$-colouring of a graph $G$ is a function
$f\colon V(G)\to \mathbb{Z}_k$ such that $f(u)\neq f(v)$ for every edge $uv$ of
$G$. A $k$-colouring of $G$ is called a $k$-star colouring of $G$ if there is
no path $u,v,w,x$ in $G$ with $f(u)=f(w)$ and $f(v)=f(x)$. A $k$-colouring of
$G$ is called a $k$-rs colouring of $G$ if there is no path $u,v,w$ in $G$ with
$f(v)>f(u)=f(w)$. For $k\in \mathbb{N}$, the problem $k$-STAR COLOURABILITY
takes a graph $G$ as input and asks whether $G$ admits a $k$-star colouring.
The problem $k$-RS COLOURABILITY is defined similarly. Recently, Brause et al.
(Electron. J. Comb., 2022) investigated the complexity of 3-star colouring with
respect to the graph diameter. We study the complexity of $k$-star colouring
and $k$-rs colouring with respect to the maximum degree for all $k\geq 3$. For
$k\geq 3$, let us denote the least integer $d$ such that $k$-STAR COLOURABILITY
(resp. $k$-RS COLOURABILITY) is NP-complete for graphs of maximum degree $d$ by
$L_s^{(k)}$ (resp. $L_{rs}^{(k)}$).
  We prove that for $k=5$ and $k\geq 7$, $k$-STAR COLOURABILITY is NP-complete
for graphs of maximum degree $k-1$. We also show that $4$-RS COLOURABILITY is
NP-complete for planar 3-regular graphs of girth 5 and $k$-RS COLOURABILITY is
NP-complete for triangle-free graphs of maximum degree $k-1$ for $k\geq 5$.
Using these results, we prove the following: (i) for $k\geq 4$ and $d\leq k-1$,
$k$-STAR COLOURABILITY is NP-complete for $d$-regular graphs if and only if
$d\geq L_s^{(k)}$; and (ii) for $k\geq 4$, $k$-RS COLOURABILITY is NP-complete
for $d$-regular graphs if and only if $L_{rs}^{(k)}\leq d\leq k-1$.
