  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 $f\colon E(G) \to E(H)$ such
that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$.
For every $r\geq 3$, let $\mathcal{H}_r$ be an inclusion-wise minimal set of
connected $r$-graphs, such that for every connected $r$-graph $G$ there is an
$H \in \mathcal{H}_r$ which colors $G$.
  We show that $\mathcal{H}_r$ is unique and characterize $\mathcal{H}_r$ by
showing that $G \in \mathcal{H}_r$ if and only if the only connected $r$-graph
coloring $G$ is $G$ itself.
  The Petersen Coloring Conjecture states that the Petersen graph $P$ colors
every bridgeless cubic graph. We show that if true, this is a very exclusive
situation. Indeed, either $\mathcal{H}_3 = \{P\}$ or $\mathcal{H}_3$ is an
infinite set and if $r \geq 4$, then $\mathcal{H}_r$ is an infinite set.
Similar results hold for the restriction on simple $r$-graphs.
  By definition, $r$-graphs of class $1$ (i.e. those having edge-chromatic
number equal to $r$) can be colored with any $r$-graph. Hence, our study will
focus on those $r$-graphs whose edge-chromatic number is bigger than $r$, also
called $r$-graphs of class $2$. We determine the set of smallest $r$-graphs of
class 2 and show that it is a subset of $\mathcal{H}_r$.
