Locally identifying colourings for graphs with given maximum degree

DOI10.1016/J.DISC.2012.01.034MaRDI QIDQ418899zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1869706 (Why is no real title available?)
• scientific article; zbMATH DE number 907924 (Why is no real title available?)
• k-Degenerate Graphs
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Graph Classes: A Survey
• Graph theory
• On a new class of codes for identifying vertices in graphs
• Vertex-distinguishing edge colorings of graphs
• Vertex-distinguishing proper edge-colorings

Cited in

(10)

• 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
• Locally identifying coloring of graphs with few P4s
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• Inapproximability of the lid-chromatic number
• Locally identifying coloring of graphs
• Extension of universal cycles for globally identifying colorings of cycles
• Locally identifying coloring in bounded expansion classes of graphs
• On locally identifying coloring 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)