Progress on the Adjacent Vertex Distinguishing Edge Coloring Conjecture
Gwenaël Joret, William Lochet · SIAM Journal on Discrete Mathematics · 2020
A proper edge coloring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colors. Using a clever application of the local lemma, Hatami [ J. Combin. Theory Ser. B, 95 (2005), pp. 246--256] proved that every graph with maximum degree $\Delta$ and no isolated edge has an adjacent vertex distinguishing edge coloring with $\Delta + 300$ colors, 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 [ Appl. Math. Lett., 15 (2002), pp. 623--626] that $\Delta + 2$ colors are enough for $\Delta \geqslant 3$.