Locally identifying coloring of graphs with few P4s

A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv, if u and v have distinct closed neighborhoods, then the set of colors used on vertices of the closed neighborhoods of u and v are distinct. The lid-chromatic number is the minimum number of colors used in a lid-coloring. In this paper we prove 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, such as cographs, P4-sparse graphs and (q,q−4)-graphs. We also prove that the lid-chromatic number is O(n1−ε)-inapproximable in polynomial time for every ε>0, unless P=NP.