Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number. Issue 4 (16th October 2018)

• Record Type: Journal Article
• Authors: Kwaśny, Jakub; Przybyło, Jakub
• Is Part Of: Random structures & algorithms. Volume 54:Issue 4(2019)
• Page Start: 768
• Page End: 778
• Publication Date: 2018-10-16
• Subjects: adjacent vertex distinguishing edge choice number -- adjacent vertex distinguishing edge coloring -- adjacent vertex distinguishing total coloring -- list neighbor set distinguishing index; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20813
• Languages: English
• ISSNs: 1042-9832

Abstract

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.