COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	STAN-CS-80-830
C00004 ENDMK
C⊗;
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.