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

D e l t a + C D e l t a^{f r a c 12} (l o g D e l t a)^{4}

, where

D e l t a

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.

Recommendations

Cited in

(8)

This page was built for publication: Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number