Locally identifying coloring of graphs (Q456289)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Locally identifying coloring of graphs |
scientific article |
Statements
Locally identifying coloring of graphs (English)
0 references
24 October 2012
0 references
Summary: 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_{\text{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_{\text{lid}}\) for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether \(\chi_{\text{lid}}(G)=3\) for a subcubic bipartite graph \(G\) with large girth is an NP-complete problem.
0 references
subcubic bipartite graph
0 references
identifying code
0 references