Abstract
A locally identifying coloring (lid-coloring) of a graph is a proper vertex-coloring such that the sets of colors appearing in the closed neighborhoods of any pair of adjacent vertices having distinct neighborhoods are distinct. Our goal is to study a relaxed locally identifying coloring (rlid-coloring) of a graph that is similar to locally identifying coloring for which the coloring is not necessarily proper. We denote by \(\chi _{rlid}(G)\) the minimum number of colors used in a relaxed locally identifying coloring of a graph G. In this paper, we prove that the problem of deciding that \(\chi _{rlid}(G)=3\) for a 2-degenerate planar graph G is NP-complete and for a bipartite graph G is polynomial. We give several bounds of \(\chi _{rlid}(G)\) for different families of graphs and construct new graphs for which these bounds are tight. We also compare this parameter with the minimum number of colors used in a locally identifying coloring of a graph G (\(\chi _{lid}(G)\)), the size of a minimum identifying code of G (\(\gamma _{id}(G)\)) and the chromatic number of G (\(\chi (G)\)).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Esperet, L., Gravier, S., Montassier, M., Ochem, P., Parreau, A.: Locally identifying coloring of graphs. Electron. J. Comb. 19(2), P40 (2012)
Foucaud, F., Honkala, I., Laihonen, T., Parreau, A., Perarnau, G.: Locally identifying colourings for graphs with given maximum degree. Discrete Math. 312(10), 1832–1837 (2012)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Computer Sci. 1, 237–267 (1976)
Gonçalves, D., Parreau, A., Pinlou, A.: Locally identifying coloring in bounded expansion classes of graphs. Discrete Appl. Math. 161(18), 2946–2951 (2013)
Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory 44, 599–611 (1998)
Parreau, A.: Problèmes d’identification dans les graphes. PhD Thesis, Grenoble, France (2012)
Acknowledgments
Our acknowledgements go to the referees for careful reading and helpful remarks to improve this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aïder, M., Gravier, S. & Slimani, S. Relaxed Locally Identifying Coloring of Graphs. Graphs and Combinatorics 32, 1651–1665 (2016). https://doi.org/10.1007/s00373-016-1677-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-016-1677-z