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.