### Absolute Reducibility of Maps of at Most 19 Regions

The Johns Hopkins University, 1966

Abstract

Birkhoff and Lewis have proposed a strong form of the 4-color conjecture
in terms of chromatic polynomials, and verified, by actual computation,
that this conjecture holds for certain regular maps with at most 17
regions. They have also shown that in a cubic map of simply connected
regions, a proper 2-ring, a proper 3-ring, and a 4-sided region surrounded
by a proper 4-ring are absolutely reducible configurations, that is, that
their presence in a map assures us that the Birkhoff-Lewis conjecture
holds for the given map if it holds for all other maps with fewer regions
than the given map. However, it has not been shown that a pentagon is an
absolutely reducible configuration.

As a consequence of the Euler polyhedral formula, it has been shown that
every cubic map with fewer than 12 regions has a region with fewer than 5
sides, and hence is an absolutely reducible configuration. If a cubic map
with a least 12 regions has no region with fewer than 5 sides, it has at
least 12 pentagons. Hence a proof that a pentagon is an absolutely
reducible configuration would confirm the Birkhoff-Lewis conjecture, and
therefore the 4-color conjecture.

A regular map which contains no region with fewer than 5 sides is called a
regular major map.

By deriving some of the properties of regular major maps, all such maps
with fewer than 20 regions were determined within homeomorphisms in this
paper. The chromatic polynomials of these maps have been calculated, and
it was confirmed that the Birkhoff-Lewis conjecture holds in each case.
From the fact that all other cubic maps with fewer than 20 regions contain
at least one absolutely reducible configuration, it follows that the
Birkhoff-Lewis conjecture holds for all maps with fewer than 20 regions.