Definition (informal) A normal edge-5-coloring of a bridgeless cubic graph $G$ is a proper 5 coloring of the edges of the graph, so that for each edge $e\in E(G)$, either $e$ and the four edges adjacent to it are colored with five colors, or they are colored with three colors.
Several decades ago, Jaeger proposed the following conjecture, which implies several (two) of the most notorious outstanding problems in graph theory (for example, the Berge-Fulkerson conjecture, and the cycle double cover conjecture).
Conjecture 1 [Jaeger, 1980, 1985] Every bridgeless cubic graph has a normal edge-5-coloring.
Our question concerns a special case of this conjecture.
Question Let $G$ be a bridgeless cubic graph that has a Hamiltonian path. Does $G$ have a normal edge-5-coloring? As always, the intent of the question is to provide proof or counterexample.
Clearly, Hamiltonian graphs have a normal edge-5-coloring (in fact, an edge-3-coloring). Here, we relax the hamiltonicity condition to be one that requires Hamiltonian paths, and not necessarily Hamiltonian cycles. We believe that the condition is strong enough that a proof of it might be within reach, perhaps an algorithmic one. It is also a light enough condition that many graphs, including snarks, satisfy, in particular if their cyclic connectivity is high.
For an interesting paper on normal colorings, see [1].
[1] ˘Sámal, R., New approach to Petersen coloring, Electronic Notes in Discrete Mathematics 38 (2011) 755-760
