Progress on the adjacent vertex distinguishing edge colouring conjecture

Abstract

A proper edge colouring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colours. Using a clever application of the Local Lemma, Hatami (2005) proved that every graph with maximum degree $\Delta$ and no isolated edge has an adjacent vertex distinguishing edge colouring with $\Delta +300$ colours, provided $\Delta$ is large enough. We show that this bound can be reduced to $\Delta +19$. This is motivated by the conjecture of Zhang, Liu, and Wang (2002) that $\Delta +2$ colours are enough for $\Delta \ge 3$.

v2: Revised following referees' comments

References in corpus (7)

• Acyclic edge-coloring using entropy compression
• Nonrepetitive Colouring via Entropy Compression
• A new approach to nonrepetitive sequences
• The Local Cut Lemma
• On the neighbour sum distinguishing index of planar graphs
• A note on asymptotically optimal neighbour sum distinguishing colourings
• Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number