  We introduce the notion of locally identifying coloring of a graph. A proper
vertex-coloring c of a graph G is said to be locally identifying, if for any
adjacent vertices u and v with distinct closed neighborhood, the sets of colors
that appear in the closed neighborhood of u and v are distinct. Let
$\chi_{lid}(G)$ be the minimum number of colors used in a locally identifying
vertex-coloring of G. In this paper, we give several bounds on $\chi_{lid}$ for
different families of graphs (planar graphs, some subclasses of perfect graphs,
graphs with bounded maximum degree) and prove that deciding whether
$\chi_{lid}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an
NP-complete problem.
