Locally identifying colourings for graphs with given maximum degree

Details Locally identifying colourings for graphs with given maximum degree Locally identifying colourings for graphs with given maximum degree

2011-08-13

arxiv.org/abs/1108.2769v2

Mathematics

Combinatorics

Scientific paper

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 $2\Delta^2-3\Delta+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.

Affiliated with

Also associated with

No associations

Rating

Locally identifying colourings for graphs with given maximum degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Locally identifying colourings for graphs with given maximum degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locally identifying colourings for graphs with given maximum degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636347