A note on local coloring 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). Chartrand et al. [2] asked: does there exist a graph G(k) such that chi(l)(G(k)) = chi (G(k)) = k? Furthermore, they conjectured that for every positive integer k, there exists a graph G(k) with chi(l)(G) = k such that every local k-coloring of G(k) uses all of the colors 1, 2, ..., k. In this paper we give a affirmative answer to the problem and confirm the conjecture. (C) 2014 Published by Elsevier B.V.