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:
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 email@example.com and to firstname.lastname@example.org
August, 1995. Modified November, 1998