perm filename ABST.830[BIB,CSR] blob sn#568237
filedate 1981-03-03 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00002 00002 STAN-CS-80-830
Two Linear-Time Algorithms for Five-Coloring a Planar Graph
by David Matula, Yossi Shiloach and Robert Tarjan (23 pages, December 1980)
A "sequential processing" algorithm using bicolor interchange that five-
colors an %2n%1 vertex planar graph in O(%2n%1↑2) time was given by Matula,
Marble, and Isaacson [MMI 72]. Lipton and Miller used a "bach processing"
algorithm with bicolor interchange for the same problem and achieved an improved
O(%2n%1 log %2n%1)time bound [LM 78]. 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(%2n%1) time.