Sept. 2 3:30pm, Wean 8220

Oleg Pikhurko CMU

All large trees are prime

Oleg Pikhurko CMU

All large trees are prime

Abstract:

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.