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