Locally identifying coloring of graphs

Louis Esperet (1) , Sylvain Gravier (2) , Mickael Montassier (3) , Pascal Ochem (4) , Aline Parreau (2)

1 G-SCOP_OC - Optimisation Combinatoire
2 IF - Institut Fourier
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
4 LRI - Laboratoire de Recherche en Informatique

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.

Mots clés: identifying code; distinguishing coloring

Domaines: Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Louis Esperet, Sylvain Gravier, Mickael Montassier, Pascal Ochem, Aline Parreau. Locally identifying coloring of graphs. The Electronic Journal of Combinatorics, 2012, 19 (2), pp.40. ⟨hal-00529640v2⟩