Inapproximability of the lid-chromatic number

A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv where u and v have distinct closed neighborhoods, the set of colors used on vertices of the closed neighborhoods of u and v are also distinct. In this paper we obtain a relation between lid-coloring and a variation, called strong lid-coloring. With this, we obtain linear time algorithms to calculate the lid-chromatic number for some classes of graphs with few P4's. We also prove that the lid-chromatic number is O(n1/2−ε)-inapproximable in polinomial time for every ε>0, unless P=NP.