to appear in European Journal of Combinatorics.
Coloring zonotopal quadrangulations of the projective space
by Masahiro Hachimori, Atsuhiro Nakamoto, Kenta Ozeki
Abstract
A quadrangulation on a surface F^2 is a map of a simple graph on F^2 such that
each 2-dimensional face is a quadrilateral. Youngs proved that every quadrangulation
on the projective plane P^2 is either bipartite or 4-chromatic. It is a surprising result
since every quadrangulation on an orientable surface with sufficiently high edge-width
is 3-colorable. Kaiser and Stehlík defined a d-dimensional quadrangulation Q on the d-dimensional
projective space P^d for any d ≥ 2, and proved that Q has chromatic number
at least d+2 if Q is not bipartite. In this paper, we define another kind of d-dimensional
quadrangulations Q of Pd for any d ≥ 2, and prove that Q is always 4-chromatic if Q is
non-bipartite and satisfies a special geometric condition related to a zonotopal tiling of a
d-dimensional zonotope.