Journal of Combinatorics

Volume 2 (2011)

Number 4

Primality of trees

Pages: 481 – 500



Penny Haxell (Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada)

Oleg Pikhurko (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Penn., U.S.A.)

Anusch Taraz (Zentrum Mathematik, Technische Universität München, Germany)


A graph of order $n$ is $prime$ if one can bijectively label its vertices with integers $1,\dots,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.


coprime graph, prime labeling, Entringer–Tout conjecture

2010 Mathematics Subject Classification


Full Text (PDF format)