Agnes Scott College

Ruth A. Bari

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.