Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number. Issue 4 (16th October 2018) - Kwaśny, Jakub; Przybyło, Jakub
Abstract: An adjacent vertex distinguishing edge coloring of a graph G without isolated edges is its proper edge coloring such that no pair of adjacent vertices meets the same set of colors in G . We show that such coloring 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 Δ + C Δ 1 2 ( log Δ ) 4, where Δ is the maximum degree of G and C is a constant. The proof is probabilistic. The same is true in the environment of total colorings.