Locally Identifying Coloring of Graphs

Abstract

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 neighborhoods, the sets of colors that appear in the closed neighborhood of $u$ and $v$, respectively, are distinct. Let $\chi_{\rm{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_{\rm{lid}}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $\chi_{\rm{lid}}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem.