Anais do Simpósio Brasileiro de Pesquisa Operacional
Proceedings of LVI Brazilian Symposium on Operations Research

A locally identifying coloring (or lid-coloring for short) in a graph is a proper vertex 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 of a graph $G$, denoted by $\chi_{lid}(G)$, is the minimum number of colors needed in any lid-coloring of $G$. In this work, we show that deciding whether a corona graph $G$ has a lid-coloring of size at most $k$ is an $\NP$-complete problem. Moreover, we determine the exact values and bounds for the lid-chromatic number for the corona of two complete graphs.