Locally injective kk-colourings of planar graphs

A colouring of the vertices of a graph is called injective if every two distinct vertices connected by a path of length 2 receive different colours, and it is called locally injective if it is an injective proper colouring. We show that for k≥4k≥4, deciding the existence of a locally injective kk-colouring, and of an injective kk-colouring, are NPNP-complete problems even when restricted to planar graphs. It is known that every planar graph of maximum degree ≤35k−52 allows a locally injective kk-colouring. To compare the behaviour of planar and general graphs we show that for general graphs, deciding the existence of a locally injective kk-colouring becomes NPNP-complete for graphs of maximum degree 2k (when k≥7k≥7).