
Discrete Mathematics and Optimization Seminar

DEC. 3, 2008 MC 320, 4:00PM
On the coprimality graph
Penny Haxell
University of Waterloo

A conjecure of Entringer states that the vertex set of every tree with
n vertices can be labelled 1 to n such that any two adjacent vertices
get coprime labels. We prove this for all large n by considering the
coprimality graph S(n) with n vertices, whose vertex set consists of
the integers from 1 to n, where i and j are joined by an edge if and
only if they are coprime. Then Entringer's conjecture says that every
tree with n vertices is a subgraph of S(n). We also show that various
other classes of graphs always appear as spanning subgraphs of
S(n). This represents joint work with Oleg Pikhurko and Anusch Taraz.



