A Petersen coloring (or 
-coloring) of a cubic graph
is a map from its edges to
the edges of the Petersen
graph that sends the three edges incident with
each graph vertex to the three edges
incident with some graph vertex of the Petersen
graph. The name refers to the use of the edges
of the Petersen graph as colors, with their incidence
pattern preserved at each graph vertex (Jaeger 1988).
The illustration above shows a Petersen coloring of the Petersen graph itself, with the numbers identifying the 15 edges used as colors.
The tetrahedral graph 
also admits a Petersen coloring, as illustrated above with
on the left and the Petersen
graph on the right. Matching colors and numbers identify the map
between their edges. Each graph
vertex of 
has one incident graph edge of each of the three colors
labeled 1, 2, and 3. These three colors are the edges
incident with a single graph vertex of the Petersen
graph, so the required incidence condition holds at every graph
vertex of 
.
This example also shows that a Petersen coloring need not use all 15 edges
of the Petersen graph as colors.
Jaeger's now-refuted Petersen coloring conjecture asserted that every bridgeless graph that is cubic admits a Petersen coloring.
