Rainbow trees and graceful labellings.

Abstract: A tree T on n vertices is said to be graceful if there exists a bijective labelling f of its vertices to the set {1,2,…,n} such that the values of |f(x)-f(y)| are pairwise distinct over all edges xy in E(T), or equivalently, such that the set {|f(x)-f(y)| : xy in E(T)} has size exactly n-1. The longstanding graceful tree conjecture, posed by Rósa in the 1960s, asserts that every tree is graceful.

We prove an approximate version of this conjecture by showing that every tree T on n vertices has a bijective labelling f of its vertices to the set {1,2,…,n} such that the set {|f(x)-f(y)| : xy in E(T)} has size (1-o(1))n.  In other words, every sufficiently large tree is almost graceful. In this talk, we discuss examples of such labellings, an equivalent version of the conjecture that considers rainbow trees, and the methods required to prove our result.
This is joint work with Shoham Letzter and Alexey Pokrovskiy.

Posted on Mar 30, 2026 in Seminario de Grafos, Seminars