# Labellings of trees with maximum degree three - an improved bound

Brankovic, L.; Rosa, A. and Siran, J. (2005). Labellings of trees with maximum degree three - an improved bound. Journal of Combinatorial Mathematics and Combinatorial Computing, 55 pp. 159–169.

## Abstract

If is a tree on vertex set , where , a labelling of is a bijection from to . The labelling induces an edge labelling by for . The size of the labelling is . A labelling is graceful if its size is . The famous graceful tree conjecture states that every tree has a graceful labelling. This conjecture is open even for trees with maximum degree 3. A labelling of is bipartite, if there is real number that separates the labels of the natural 2-coloration of , i.e. labels from one class are below, labels from the other class are above the number. The gracesize gs is the maximum size of a labelling of , and the -size is the maximum size of a bipartite labelling of . It is not true that were always . However the paper shows that for trees with maximum degree 3 we have . Perhaps it is for some constant .