Abstract   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  P  4 's. We also prove that the lid-chromatic number is   O  (    n    1  /  2  −  e    )  -inapproximable in polinomial time for every   e  >  0  , unless P=NP.
['Nícolas A. Martins', 'Rudini Menezes Sampaio']
Inapproximability of the lid-chromatic number