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 subset of V (G), 2 <= vertical bar S vertical bar <= 3, there exist u, v is an element of S with vertical bar f (u) - f(v)vertical bar at least the size of the subgraph induced by S. The local chromatic number of G is chi(l)(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 Delta = 7 or 8. (C) 2017 Elsevier B.V. All rights reserved.