To Color the Errera Map and its Variations Using Four Colors
- Weiguo Xie,
- Andrew Bowling
Weiguo Xie
Swenson College of Science & Engineering University of Minnesota Duluth Duluth
Corresponding Author:xiew@umn.edu
Author ProfileAndrew Bowling
Swenson College of Science & Engineering University of Minnesota Duluth Duluth
Abstract
A Kempe chain in a colored graph is a maximal connected component containing at most two colors. Kempe chains have played an important role historically in the study of the Four Color Problem. Some methods of systematically applying Kempe chain color exchanges have been studied by Alfred Errera and Weiguo Xie. A map constructed by Errera represents an important counterexample to some implementations of these methods. Using the ideas of Irving Kittell, we determine all colorings of the Errera map which form such a counterexample and describe how to color them individually. We then extend our results from the Errera map to a family of graphs containing the Errera map in a specific way. Being able to color this family of graphs appears to address many cases which prove difficult for the previous systematic color exchange methods.