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] which 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 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?

[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