Edge colouring by total labellings

Brandt, Stephan; Rautenbach, Dieter GND; Stiebitz, Michael GND

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 X¬′t(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⌉ ≤ X¬′t(G) ≤ + 1. We improve the upper bound by 1 for every graph and prove a general upper bound of ¬X′t(G) ≤ /2 + O(√log). Moreover, we investigate some special classes of graphs.


Citation style:

Brandt, Stephan / Rautenbach, Dieter / Stiebitz, Michael: Edge colouring by total labellings. 2007.

Access Statistic

Last 12 Month:

open graphic


Use and reproduction:
All rights reserved