Relaxed locally identifying coloring of graphs

DOI10.1007/S00373-016-1677-ZMaRDI QIDQ343700zbMATH OpenOpenAlexFDO

Authors Meziane Aider, Souad Slimani, Sylvain Gravier

Publication date 29 November 2016

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

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

zbMATH Keywords

identifying coloringrelaxed locally identifying chromatic numbertwins

Mathematics Subject Classification ID

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

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)$).

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

Cites work

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

Cited in

(7)

• Locally identifying coloring of graphs with few P4s
• Locally identifying coloring in bounded expansion classes 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
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number 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)