Asymptotically Optimal Neighbour Sum Distinguishing Colourings of Graphs

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 chi'(Sigma)(G). The definition of this parameter, which makes sense for graphs containing no isolated edges, immediately implies that chi'(Sigma)(G) >= Delta, where Delta is the maximum degree of G. On the other hand, it was conjectured by Flandrin et al. that chi'(Sigma)(G) <= Delta + 2 for all those graphs, except for C-5. We prove this bound to be asymptotically correct by showing that chi'(Sigma)(G) <= Delta(1+o(1)). 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. (c) 2014 Wiley Periodicals, Inc.