Let G be a triangulation of some surface. For a vertex v of G, let S(v) (the star of v) denote the set of all facial triangles containing v. A local coloring is a collection of 4-colorings of all stars of vertices of G such that for every edge uv of G, there is a permutation of colors such that the coloring of S(v) and the permuted coloring of S(u) agree on two triangles they have in common. This notion of a coloring is equivalent to the usual vertex 4-coloring for planar triangulations, but is not equivalent for non-simply-connected surfaces.
Problem (Steve Fisk): Does every triangulation of an orientable surface have a local coloring?
Why the restriction to orientable surfaces? The graph K6 embedded in the projective plane has no local coloring. For more information see [1,2].
[1] S. Fisk, Combinatorial structures on triangulations. II. Local colorings, Adv. Math. 11 (1973), 339-350.
[2] S. Fisk, Variations on coloring, surfaces and higher-dimensional manifolds, Adv. Math. 25 (1977), 226-266.
Send comments to Bojan.Mohar@uni-lj.si