If T is a triangulation and we add a vertex of degree 3 to one of the triangles of T, then we say that the result is 3-equivalent to T. We extend this relation to an equivalence relation, called 3-equivalence.

If two triangulations are 3-equivalent, then their vertex 4-colorings correspond bijectively. In particular, two 3-equivalent triangulations have the same number of 4-colorings. We ask if the converse is true. It is not. Non-trivially, there are triangulations with the same number of 4-colorings that are not 3-equivalent. But, there is a rephrasing on this converse as a finiteness question:

Question: For any integer n, are there a finite number of non-3-equivalent triangulations with exactly n 4-colorings?

This would follow from a result of the form:

This is closely related to a famous conjecture, which is now a theorem (whose proof, incidently, implies the Four-Color-Theorem).

Theorem: If a plane triangulation is uniquely 4-colorable, then it can be reduced to a triangle by repeatedly deleting degree three vertices.

For a history of this conjecture see Jensen and Toft [JT page 48]. For the proof, see Fowler [F].

We turn to a similar question. Consider a 4-coloring of a triangulation T of the 2-sphere as a map f from T to the tetrahedron. Since this is a map between 2-spheres, there is a well defined integer (up to sign), the degree deg(f).

[[Note by Dan Archdeacon: the degree of a coloring can be defined in terms of the numbers of triangles receiving particular color sequences. Contact Steve Fisk for details.]]

Some basic facts about degree are:

if all vertices of T have even degree, then deg(f) is zero for all four colorings f, and

if all but two vertices of T have even degree, then deg(f) is zero for all four colorings f.

Question: If T is a triangulation of the 2-sphere such that all 4-colorings have degree 0, then is T is 3-equivalent to a triangulation with at most 2 vertices of odd degree?

[F] Tom Fowler, (I do not know the title of his paper), Georgia Technical University, Atlanta, Georgia

[JT] T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York.

Submitted by: Steve Fisk, Department of Mathematics, Bowdoin College, Brunswick ME 04011-2599 USA.

Send comments to dan.archdeacon@uvm.edu and to fisk@bowdoin.edu

August, 1995. Modified November, 1998