A finite graph on
vertices has a prime labeling provided there is a way to label the vertices with the integers
1 through
such that every pair of adjacent vertices has relatively prime labels. We
extend the definition of prime labeling to infinite graphs and give a simple
necessary and sufficient condition for an infinite graph to have a prime labeling.
We then measure the complexity of prime labelings of infinite graphs using
techniques from computability theory to verify that our condition is as simple as
possible.
Keywords
graph labelings, infinite graphs, prime labelings,
computability theory
