Edge colouring by total labellings

We introduce the concept of an edge-colouring total kk-labelling. This is a labelling of the vertices and the edges of a graph GG with labels 1,2,…,k1,2,…,k such that the weights of the edges define a proper edge colouring of GG. Here the weight of an edge is the sum of its label and the labels of its two endvertices. We define χt′(G) to be the smallest integer kk for which GG has an edge-colouring total kk-labelling. This parameter has natural upper and lower bounds in terms of the maximum degree ΔΔ of G:⌈(Δ+1)/2⌉≤χt′(G)≤Δ+1. We improve the upper bound by 1 for every graph and prove χt′(G)≤Δ/2+O(ΔlogΔ). Moreover, we investigate some special classes of graphs.