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