Three-Edge-Coloring Orientable Triangulations

The following conjecture is due to Grunbaum [Gr].

Conjecture: Any (simple) triangulation of an orientable surface can be 3-edge-colored such that each color appears around each face.

The problem is interesting in dual form. It states that the dual of any (simple) triangulation is 3-edge-colorable. At first glance this would be easy to refute: embed any non-3-edge-colorable graph and take the dual, the result would be a counterexample to the conjecture. However, the dual need not be simple.

An embedding in which two distinct faces share at most a vertex or edge in their boundaries is called polyhedral. The conjecture is equivalent to:

Conjecture: No non-3-edge-colorable graph has a polyhedral embedding.

The problem reduces to showing that no snark (see [Ga]) has a polyhedral embedding. Archdeacon, Bonnington, and Siran have examined many of the known snarks and shown that they have no polyhedral embedding (this extends and confirms earlier results of others). The search is helped by searching for poly-killers, minimal subgraphs with the property that they cannot occur in any graph with a polyhedral embedding.

The conjecture should be difficult to prove since it is strictly stronger than the 4-Color-Theorem. (Any planar triangulation could be placed in a single face of any orientable triangulation. A Grunbaum coloring of the triangulation would give the dual of a Tait coloring of the planar graph.)

The restriction to orientable surfaces is necessary, since K_6 triangulating the projective plane has no such coloring. The dual of this embedding is the Petersen graph.

A partial result would be to show that a Grunbaum coloring exists for those triangulations with every noncontractible cycle of length at least n for some large enough n depending on the surface. Setting n = 4 eliminates the projective plane counterexample, so this might be true for nonorientable surfaces as well. A second partial result would be to examine classes of triangulations. Is the conjecture true for complete graphs?

Grunbaum believes that the conjecture is true (personal communication); I believe it is false.

References:

[Ga] M. Gardner, Mathematical Games, Sci. Amer. 234 and 235 (1976) April issue pp. 126-130, September issue pp. 210-211.

[Gr] B. Grunbaum, Conjecture 6. In Recent progress in Combinatorics, (W.T. Tutte Ed.), Academic Press (1969) 343.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.