Around 1980 Entringer and Tout conjectured that every tree is prime,
that is, its vertices can be bijectively labeled with integers
1,...,n, where n is the order of the tree, so that every two adjacent
vertices get coprime labels. We prove this conjecture for all
sufficiently large n along with some extensions.
This is joint work with Penny Haxell and Anusch Taraz.
The ACO Seminar (2010-2011)