Determining Triangulations by their Four-Colorings

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:

The number of colorings of a triangulation with no vertices of degree 3 goes to infinity as the number of vertices goes to infinity.

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 vertices of
- if all but two vertices of
*T*have even degree, then*deg(f)*is zero for all four colorings*f*.- if all but two vertices of

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

References:

[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