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