Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number

Abstract

An adjacent vertex distinguishing edge colouring of a graph $G$ without isolated edges is its proper edge colouring such that no pair of adjacent vertices meets the same set of colours in $G$. We show that such colouring can be chosen from any set of lists associated to the edges of $G$ as long as the size of every list is at least $\Delta +C{\Delta }^{\frac{1}{2}}(\log \Delta {)}^4$, where $\Delta$ is the maximum degree of $G$ and $C$ is a constant. The proof is probabilistic. The same is true in the environment of total colourings.

12 pages

Cited by in corpus (1)

• Progress on the adjacent vertex distinguishing edge colouring conjecture