Sets of r-Graphs that Color All r-Graphs

An r-regular graph is an r-graph, if every odd set of vertices is connected to its complement by at least r edges. Let G and H be r-graphs. An H-coloring of G is a mapping such that each r adjacent edges of G are mapped to r adjacent edges of H. For every , let be an inclusion-wise minimal set of connected r-graphs, such that for every connected r-graph G there is an which colors G. The Petersen Coloring Conjecture states that consists of the Petersen graph P. We show that if true, then this is a very exclusive situation. Our main result is that either or is an infinite set and if , then is an infinite set. In particular, for all , is unique. We first characterize and then prove that if contains more than one element, then it is an infinite set. To obtain our main result we show that contains the smallest r-graphs of class 2 and the smallest poorly matchable r-graphs, and we determine the smallest r-graphs of class 2.