Report Number: CS-TR-80-830
Institution: Stanford University, Department of Computer Science
Title: Two linear-time algorithms for five-coloring a planar graph
Author: Matula, David W.
Author: Shiloach, Yossi
Author: Tarjan, Robert E.
Date: November 1980
Abstract: A "sequential processing" algorithm using bicolor interchange that five-colors an n vertex planar graph in $O(n^2)$ time was given by Matula, Marble, and Isaacson [1972]. Lipton and Miller used a "batch processing" algorithm with bicolor interchange for the same problem and achieved an improved O(n log n) time bound [1978]. In this paper we use graph contraction arguments instead of bicolor interchange and improve both the sequential processing and batch processing methods to obtain five-coloring algorithms that operate in O(n) time.