An embedding of a graph G in some surface is said to be polyhedral if every facial boundary is a cycle in the graph and any two distinct faces share at most a vertex or an edge in their boundaries. It is easy to see that an embedding is polyhedral if and only if the graph is 3-connected and the face-width is at least 3.
The following conjecture is due to Grunbaum .
Conjecture (Grunbaum, 1969): If a cubic graph has a polyhedral embedding in an orientable surface, then it is 3-edge-colorable.
The conjecture should be difficult to prove since it is strictly stronger than the 4-Color-Theorem. The restriction to orientable surfaces is necessary, since the Petersen graph has a polyhedral embedding in the projective plane.
Grunbaum told me in 1988 that he originally thought that the conjecture should be false. Archdeacon claims that "Grunbaum believes that the conjecture is true". (Here we speak about the recent opinion of the proposer.)
The following relaxation of Grunbaum's conjecture has been proposed by Mohar (for orientable surfaces) and Robertson (for arbitrary surfaces).
Conjecture (Mohar and Robertson, 1988). There is a fixed constant k such that every 2-connected cubic graph with an (orientable) embedding of face-width at least k has a 3-edge-coloring.
Conjecture (Robertson, 1992). There is a fixed constant k such that every 2-connected graph with an embedding of face-width at least k has a nowhere-zero 4-flow.
 B. Grunbaum, Conjecture 6. In Recent progress in Combinatorics, (W.T. Tutte Ed.), Academic Press (1969) 343.
Send comments to Bojan.Mohar@uni-lj.si