Some color-critical subgraphs of prime distance graphs

             Roger Eggleton, Paul Erdos and Aviezri Fraenkel

   ABSTRACT. The problem of determining which prime distance graphs on the 
integers are 4-chromatic remains open. Here we consider which 4-chromatic
color-critical graphs (minimal 4-chromatic graphs) can occur in prime 
distance graphs. We show that odd wheels of only three distinct orders 
occur in prime distance graphs, and occur if and only if distances 2, 3, 5 
and 7 are all present. In contrast we also show that generalized Groetsch 
graphs of at least four different orders occur, and each occurs in a 
potential infinitude of independent prime distance graphs.