## Grunbaum's Edge-Coloring Conjecture

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
[1].

**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.

**
****References:**

[1] 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

##### Revised: junij 15, 2001.