BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-80-830
       ENTRY:: June 08, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Two linear-time algorithms for five-coloring a planar graph
        TYPE:: Technical Report
      AUTHOR:: Matula, David W.
      AUTHOR:: Shiloach, Yossi
      AUTHOR:: Tarjan, Robert E.
        DATE:: November 1980
       PAGES:: 26
    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 [1972]. 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 [1978]. 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.
       NOTES:: [Adminitrivia V1/Prg/19950608]
         END:: STAN//CS-TR-80-830