NP-completeness of local colorings of graphs

A local k-coloring of a graph G is a function f:V(G)→{1,2,⋯,k} such that for each S⊆V(G), 2≤|S|≤3, there exist u,v∈S with |f(u)−f(v)| at least the size of the subgraph induced by S. The local chromatic number of G is χℓ(G)=min⁡{k:G has a local k-coloring}. In this paper, we show that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t−1, where t≥3. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree Δ=7 or 8.