Mapping Planar Graphs onto Cycles

A homomorphism from G to H is a map from the vertices of G to the vertices of H such that adjacent vertices map to adjacent vertices. A homomorphism onto a 3-cycle is equivalent to a proper 3-coloring of G.

Conjecture: If G is planar and of girth at least 4k, then it has a homomorphism to the cycle of length 2k + 1.

The requirement that the girth of G is at least 4k cannot be loosened. Let G_k be the graph the graph formed by a wheel with 4k-1 spokes, where each spoke is replace by a path on 2k-1 edges. Then G has girthh 4k-1, but there is no isomorphism onto a cycle of length 2k + 1.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA. (with thanks to Matt DeVos)

Send comments to

December 2003.