Abstrakt
Petersen coloring (defined by Jaeger [On graphic-minimal spaces, Ann. Discrete Math. 8 (1980)]) is a mapping from the edges of a cubic graph to the edges of the Petersen graph, so that three edges adjacent at a vertex are mapped to three edges adjacent at a vertex.
The existence of such mapping for every cubic bridgeless graph is known to imply the truth of the Cycle double cover conjecture and of the Berge-Fulkerson conjecture. We develop Jaegerʼs alternate formulation of Petersen coloring in terms of special five-edge colorings.
We suggest a weaker conjecture, and provide new techniques to solve it. On a related note, we provide a counterexample to a stronger conjecture by DeVos, Nešetřil, and Raspaud [On edge-maps whose inverse preserves flows and tensions, Graph Theory in Paris, 2006] that asked for an oriented version of Petersen coloring.
Keywords: Petersen coloring; nowhere-zero flows; cycle-double cover