  A prime labeling of a graph of order $n$ is a labeling of the vertices with
the integers $1$ to~$n$ in which adjacent vertices have relatively prime
labels. A coprime labeling maintains the same criterion on adjacent vertices
using any set of distinct positive integers. In this paper, we consider several
families of graphs or products of graphs that have been shown to not have prime
labelings and answer the natural question of how to label the vertices while
minimizing the largest value in its set of labels.
