Locally identifying coloring of graphs

MaRDI QIDQ456289zbMATH OpenFDO

Authors L. Esperet, Sylvain Gravier, Pascal Ochem, Aline Parreau, Mickaël Montassier

Publication date 24 October 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.5624, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p40

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

identifying codesubcubic bipartite graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $ch{i}_{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 $ch{i}_{lid}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $ch{i}_{lid}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem.

Recommendations

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

Cited in

(17)

• Locating-domination and identification
• Relaxed locally identifying coloring of graphs
• On locally identifying coloring of Cartesian product and tensor product of graphs
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
• Locally identifying coloring in some chordal graphs
• Locally identifying coloring of graphs with few P4s
• Optimal local identifying and local locating-dominating codes
• Locally identifying colourings for graphs with given maximum degree
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• scientific article; zbMATH DE number 2097236 (Why is no real title available?)
• New bounds and constructions for neighbor-locating colorings of graphs
• Inapproximability of the lid-chromatic number
• Locality of not-so-weak coloring
• Locally identifying coloring in bounded expansion classes of graphs
• A Vizing-like theorem for union vertex-distinguishing edge coloring
• On locally identifying coloring of graphs

This page was built for publication: Locally identifying coloring of graphs

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