The neighbour sum distinguishing relaxed edge colouring

A k-edge colouring (not necessarily proper) of a graph with colours in {1,2,…,k} is neighbour sum distinguishing if, for any two adjacent vertices, the sums of the colours of the edges incident with each of them are distinct. The smallest value of k such that such a colouring of G exists is denoted by χ∑e(G). When we add the additional restriction that the k-edge colouring must be proper, then the smallest value of k such that such a colouring exists is denoted by χ∑′(G). Such colourings are studied on a connected graph on at least 3 vertices. There are two famous conjectures on these edge colourings: the 1-2-3 Conjecture states that χ∑e(G)≤3 for any graph G; and the other states that χ∑′(G)≤Δ(G)+2 for any graph G≠C5. In this paper, we generalize these two versions of neighbour sum distinguishing edge colourings by introducing the edge colouring in which each monochromatic set of edges induces a subgraph with maximum degree at most d. We call such an edge colouring that distinguishes adjacent vertices a neighbour sum distinguishing d-relaxed k-edge colouring. We denote by χ∑′d(G) the smallest value of k such that such a colouring of G exists. We study families of graphs for which χ∑′ is known. We show that the number of required colours decreases when the proper condition is relaxed. In particular, we prove that χ∑′2(G)≤4 for every subcubic graph. For complete graphs, we show that χ∑′d(Kn)≤4 if d∈{⌈n−12⌉,…,n−1} and we also determine the exact value of χ∑′2(Kn). Finally, we determine the value of χ∑′d(T) for any tree T.