Asymptotically optimal neighbour sum distinguishing colourings of graphs1. Issue 4 (9th June 2014) - Przybyło, Jakub
Abstract 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk524" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />χ′∑(G)</alternatives>. The definition of this parameter, which makes sense for graphs containing no isolated edges, immediately implies that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk4z3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />χ′∑(G)≥Δ</alternatives>, where Δ is the maximum degree of G. On the other hand, it was conjectured by Flandrin et al. that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk4w2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />χ′∑(G)≤Δ+2</alternatives> for all those graphs, except for C5. We prove this bound to be asymptotically correct by showing that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk4xk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />χ′∑(G)≤Δ(1+o(1))</alternatives>. 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