Advertisement
Published in:
2006 | OriginalPaper | Chapter
Quadrangulations and 5-critical Graphs on the Projective Plane
Author : Bojan Mohar
Published in: Topics in Discrete Mathematics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.