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 . 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 . 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