Strong $k$-colorings of graphs

We say that a $k$-colouring $C_1,\ldots,C_k$ of a graph $G$ is strong if for any vertex $u\in VG$ there exists an index $i\in\{1,\ldots,k\}$ such that $u$ is adjacent to any vertex of the class $C_i$. We consider the class $S(k)$ of strongly $k$-colourable graphs and demonstrate that the problem to recognise $S(k)$ is NP-complete for any $k\ge 4$, whereas it is polynomially solvable for $k=3$. We characterise the class $S(3)$ in terms of forbidden induced subgraphs and solve the problem of uniqueness of a strong 3-colouring.