Primality of trees
Penny E. Haxell, Oleg Pikhurko, Anusch Taraz · Journal of Combinatorics · 2011
A graph of order n is prime if one can bijectively label its vertices with integers 1, . . ., n so that any two adjacent vertices get coprime labels.We prove that all bipartite d-degenerate graphs with separators of size at most n 1-O d (1/ ln ln n) are prime.It immediately follows that all large trees are prime, confirming an old conjecture of Entringer and Tout from around 1980.Also, our method allows us to determine the smallest size of a non-prime connected order-n graph for all large n, proving a conjecture of Rao [R. C. Bose Centenary Symposium on Discrete Math.and Applications, Kolkata, 2002] in this range.