Asymptotically optimal neighbour sum distinguishing colourings of graphs
Jakub Przybyło · Random Structures and Algorithms · 2014
Consider a simple graph G = (V,E) and its proper edge colouring c with the elements of the set {1,2,…,k}. The colouring c is said to be neighbour sum distinguishing if for every pair of vertices u, v adjacent in G, the sum of colours of the edges incident with u is distinct from the corresponding sum for v. The smallest integer k for which such colouring exists is known as the neighbour sum distinguishing index of a graph and denoted by . The definition of this parameter, which makes sense for graphs containing no isolated edges, immediately implies that , where Δ is the maximum degree of G. On the other hand, it was conjectured by Flandrin et al. that for all those graphs, except for C5. We prove this bound to be asymptotically correct by showing that . The main idea of our argument relays on a random assignment of the colours, where the choice for every edge is biased by so called attractors, randomly assigned to the vertices. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 776–791, 2015