2018/03/05 by Hocquard, Hervé, Przybyło, Jakub
#05C15 #05C78 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1803.02686
A proper total k-colouring of a graph G=(V,E) is an assignment c : V ∪ E→ \1,2,…,k\ of colours to the edges and the vertices of G such that no two adjacent edges or vertices and no edge and its end-vertices are associated with the same colour. A total neighbour sum distinguishing k-colouring, or tnsd k-colouring for short, is a proper total k-colouring such that ∑e\ni uc(e)+c(u)≠ ∑e\ni vc(e)+c(v) for every edge uv of G. We denote by χ''Σ(G) the total neighbour sum distinguishing index of G, which is the least integer k such that a tnsd edge k-colouring of G exists. It has been conjectured that χ''Σ(G) ≤ Δ(G) + 3 for every graph G. In this paper we confirm this conjecture for any graph G with \rm mad(G)