Relaxed locally identifying coloring of graphs

DOI10.1007/S00373-016-1677-ZzbMATH Open1351.05070arXiv1406.3683OpenAlexW218747463MaRDI QIDQ343700FDOQ343700

Authors: Meziane Aider, Souad Slimani, Sylvain Gravier 

Publication date: 29 November 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A extit{locally identifying coloring} ($lid$-coloring) of a graph is a proper 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 extit{relaxed locally identifying coloring} ($rlid$-coloring) of a graph that is similar to locally identifying coloring for which the coloring is not necessary proper.We denote by $ch{i}_{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 $ch{i}_{rlid}(G)=3$ for a $2$-degenerate planar graph $G$ is $NP$-complete. We give several bounds of $ch{i}_{rlid}(G)$ and construct graphs for which some of these bounds are tightened. Studying some families of graphs allows us to compare this parameter with the minimum number of colors used in a locally identifying coloring of a graph $G$ ($ch{i}_{lid}(G)$), the size of a minimum identifying code of $G$ ($gamm{a}_{id}(G)$) and the chromatic number of $G$ ($chi(G)$).

Full work available at URL: https://arxiv.org/abs/1406.3683

Recommendations

• Locally identifying coloring of graphs
• Locally identifying coloring in bounded expansion classes of graphs
• Locally identifying coloring of graphs with few P4s
• Inapproximability of the lid-chromatic number
• Locally identifying colourings for graphs with given maximum degree

zbMATH Keywords

twinsidentifying coloringrelaxed locally identifying chromatic number

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On a new class of codes for identifying vertices in graphs
• Some simplified NP-complete graph problems
• Locally identifying coloring in bounded expansion classes of graphs
• Locally identifying colourings for graphs with given maximum degree
• Locally identifying coloring of graphs

Cited In (7)

• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• Inapproximability of the lid-chromatic number
• Locally identifying colourings for graphs with given maximum degree
• Locally identifying coloring of graphs
• On locally identifying coloring of graphs
• Locally identifying coloring of graphs with few P4s
• Locally identifying coloring in bounded expansion classes of graphs

This page was built for publication: Relaxed locally identifying coloring of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343700)