When are there Local Colorings?

A *local coloring* is a 4-coloring of each star of a vertex such that the colorings agree (up to an arbitrary permutation) on overlapping stars. This coloring is equivalent to the usual vertex 4-coloring for a planar graph, but is not equivalent for non-simply-connected surfaces.

**Question:** *Does every triangulation of an oriented surface have a local coloring? *

Why the restriction to orientable surfaces? The quotient of the icosahedron by the antipodal map embeds in the projective plane, and has no local coloring.

There are four ways to color a triangulation and these correspond to terms of the composition series of *S_4*. The identity corresponds to a 4-coloring, *K_4* to an edge coloring, *A_4* to a Heawood coloring, and *S_4* to a local coloring. These are all equivalent for the plane, but not necessarily equivalent for other surfaces.

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