Two linear-time algorithms for five-coloring a planar graph
David W. Matula, Yossi Shiloach, Robert Endre Tarjan · Defense Technical Information Center (DTIC) · 1980
A sequential processing algorithm using bicolor interchange that five-colors an n vertex planar graph in O(n-squared) 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 O(n) time. (Author)