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 *dan.archdeacon@uvm.edu*

December 2003.