Locally identifying colourings for graphs with given maximum degree

DOI10.1016/J.DISC.2012.01.034zbMATH Open1242.05092arXiv1108.2769OpenAlexW1998597471MaRDI QIDQ418899FDOQ418899

Authors: Florent Foucaud, Tero Laihonen, Aline Parreau, Guillem Perarnau, Iiro Honkala 

Publication date: 30 May 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A proper vertex-colouring of a graph G is said to be locally identifying if for any pair u,v of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the closed neighbourhoods of u and v are different. We show that any graph G has a locally identifying colouring with $2Delt{a}^2-3Delta+3$ colours, where $Delta$ is the maximum degree of G, answering in a positive way a question asked by Esperet et al. We also provide similar results for locally identifying colourings which have the property that the colours in the neighbourhood of each vertex are all different and apply our method to the class of chordal graphs.

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

Recommendations

• Locally identifying coloring of graphs
• Locally identifying coloring in bounded expansion classes of graphs
• Relaxed locally identifying coloring of graphs
• Colouring a graph frugally
• Asymptotically optimal frugal colouring

zbMATH Keywords

identificationchordal graphsmaximum degreegraph colouring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory
• Graph Classes: A Survey
• Vertex-distinguishing proper edge-colorings
• On a new class of codes for identifying vertices in graphs
• k-Degenerate Graphs
• Vertex-distinguishing edge colorings of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Extremal cardinalities for identifying and locating-dominating codes in graphs

Cited In (10)

• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• On locally identifying coloring of Cartesian product and tensor product of graphs
• Inapproximability of the lid-chromatic number
• Locally identifying coloring of graphs
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• On locally identifying coloring of graphs
• Relaxed locally identifying coloring of graphs
• Locally identifying coloring of graphs with few P4s
• Extension of universal cycles for globally identifying colorings of cycles
• Locally identifying coloring in bounded expansion classes of graphs

This page was built for publication: Locally identifying colourings for graphs with given maximum degree

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