2019/07/29 by Lee, Catherine
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1907.12670
A coprime labeling of a graph G is a labeling of the vertices of G with distinct integers from 1 to k such that adjacent vertices have coprime labels. The minimum coprime number of G is the least k for which such a labeling exists. In this paper, we determine the minimum coprime number for several well-studied classes of graphs, including the coronas of complete graphs with empty graphs and the joins of two paths. In particular, we resolve a conjecture of Seoud, El Sonbaty, and Mahran and two conjectures of Asplund and Fox. We also provide an asymptotic for the minimum coprime number of the Erdős-Rényi random graph.