Jaeger's Petersen Coloring Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite loopless undirected graph is cubic if every vertex has degree three, and bridgeless if deleting any edge does not increase its number of components. The Petersen graph $P$ is the Kneser graph on the two-element subsets of $\{1,2,3,4,5\}$, with disjoint subsets adjacent. For a vertex $v$, $\delta_G(v)$ is the set of incident edges. A Petersen coloring is a map $f:E(G)\to E(P)$ for which each incident triple $\delta_G(v)$ maps bijectively to $\delta_P(w)$ for some $w\in V(P)$. Such an edge map is cycle-continuous: the inverse image of the edge set of any cycle of $P$ has even degree at every vertex of $G$.

Statement recorded in the supplied source.

Does every finite bridgeless cubic graph $G$ admit a Petersen coloring $f:E(G)\to E(P)$? In the equivalent normal-coloring formulation, does $G$ have a proper edge coloring $c:E(G)\to\{1,2,3,4,5\}$ such that for each edge $e=uv$, \[ \left|\{c(a):a\in(\delta_G(u)\cup\delta_G(v))\setminus\{e\}\}\right|\in\{2,4\}? \] [S2]

Short English statement

Can every bridgeless cubic graph map its incident edge triples to incident triples of the Petersen graph, equivalently admit a normal proper edge coloring with five colors?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1398 (GRAPH-011). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 François Pirot, Jean-Sébastien Sereni and Riste Škrekovski, Variations on the Petersen colouring conjecture (2019), arXiv:1905.07913v1, Section 1, Conjecture 1.1 and Proposition 1.2. https://arxiv.org/abs/1905.07913v1.