Vertices of Odd Degree in a Triangulation

Define a *color pair* of a triangulation *T* to be a pair of vertices that have the same color for every 4-coloring of *T*.

**Question:** *If a triangulation* T *of the 2-sphere has a color pair, then does* T *have exactly two vertices of odd degree*?

I believe that this question is due to B. Mohar. It is motivate by the result in [F] that asserts that the only two vertices of odd degree in a triangulation must be a color pair.

A related question concerns generating triangulations with given odd structure. If *T* is a triangulation, *odd(T)* is the set of all interior vertices of odd degree. There is a well defined group homomorphism (up to conjugacy) *phi: pi_1(T-odd(T)) --> S_3* where *pi_1* is the first fundamental group and *S_3* is the symmetric group on three letters.

It is known how to generate all triangulations of the 2-sphere, and the set of all triangulations with no vertices of odd degree. Both algorithms begin with a finite set of triangulations of the appropriate kind and apply local transformations.

**Questions:** *Given a map* phi: pi_1(T- {n points}) --> S_3, *construct all triangulations with this homomorphism. The algorithm to be used should begin with a finite set of triangulations of the appropriate kind and apply local transformations to this set. Will the same set of local transformations work for all the homomorphisms? Why is there a finite set of basis triangulations? How do you find these basis triangulations?*

References:

[F] S. Fisk, The nonexistence of colorings, *J. Combin. Theory B* **24** (1978) 247-248.

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

Send comments to *dan.archdeacon@uvm.edu* and to *fisk@bowdin.edu*

August, 1995