2006 | OriginalPaper | Chapter
Quadrangulations and 5-critical Graphs on the Projective Plane
Let
Q
be a nonbipartite quadrangulation of the projective plane. Youngs [You96] proved that
Q
cannot be 3-colored. We prove that for every 4-coloring of
Q
and for any two colors a and
b
, the number of faces
F
of
Q
, on which all four colors appear and colors a and
b
are not adjacent on
F
, is odd. This strengthens previous results that have appeared in [You96, HRS02, Moh02, CT04]. If we form a triangulation of the projective plane by inserting a vertex of degree 4 in every face of
Q
, we obtain an Eulerian triangulation
T
of the projective plane whose chromatic number is 5. The above result shows that
T
is never 5-critical. We show that sometimes one can remove two, three, or four, vertices from
T
and obtain a 5-critical graph. This gives rise to an explicit construction of 5-critical graphs on the projective plane and yields the first explicit family of 5-critical graphs with arbitrarily large edge-width on a fixed surface.
