Three-coloring triangle-free planar graphs in linear time

ABSTRACT

Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm).

We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grötzsch's theorem.

REFERENCES

• 1: K. Appel and W. Haken, Every planar map is four colorable, Part I: discharging, Illinois J. of Math. 21 (1977), 429--490.
• 2: K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Part II: reducibility, Illinois J. of Math. 21 (1977), 491--567.
• 3: Z. Dvořák, D. Král' and R. Thomas, Coloring triangle-free graphs on surfaces, accepted to SODA'09.
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: J. Gimbel and C. Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), 4555--4564.
• 6: H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 (1959), 109--120.
• 7: L. Kowalik, Fast 3-coloring triangle-free planar graphs, Algorithms---ESA 2004, 436--447, Lecture Notes in Comput. Sci. 3221, Springer, Berlin, 2004.
• 8: Lukasz Kowalik , Maciej Kurowski, Oracles for bounded-length shortest paths in planar graphs, ACM Transactions on Algorithms (TALG), v.2 n.3, p.335-363, July 2006 [doi>10.1145/1159892.1159895]
• 9: T. Nishizeki and N. Chiba, Planar graphs: theory and algorithms, Ann. Discr. Math. 32, North-Holland, Amsterdam, 1988.
• 10: B. Mohar, C. Thomassen, Graphs on Surfaces, The Johns Hopkins University Press, Baltimore and London, 2001.
• 11: Neil Robertson , Daniel Sanders , Paul Seymour , Robin Thomas, The four-colour theorem, Journal of Combinatorial Theory Series B, v.70 n.1, p.2-44, May 1997 [doi>10.1006/jctb.1997.1750]
• 12: Neil Robertson , P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, Journal of Combinatorial Theory Series B, v.45 n.2, p.212-254, Oct. 1988 [doi>10.1016/0095-8956(88)90070-6]
• 13: Wei-Kuan Shih , Wen-Lian Hsu, A new planarity test, Theoretical Computer Science, v.223 n.1-2, p.179-191, July 28, 1999 [doi>10.1016/S0304-3975(98)00120-0]
• 14: Robin Thomas , Barrett Walls, Three-coloring Klein bottle graphs of girth five, Journal of Combinatorial Theory Series B, v.92 n.1, p.115-135, September 2004 [doi>10.1016/j.jctb.2004.05.001]
• 15: Carsten Thomassen, Gro¨tzsch's 3-color theorem and its counterparts for the torus and the projective plane, Journal of Combinatorial Theory Series B, v.62 n.2, p.268-279, Nov. 1994 [doi>10.1006/jctb.1994.1069]
• 16: Carsten Thomassen, A short list color proof of Grötzsch's theorem, Journal of Combinatorial Theory Series B, v.88 n.1, p.189-192, May 2003 [doi>10.1016/S0095-8956(03)00029-7]
• 17: Carsten Thomassen, The chromatic number of a graph of girth 5 on a fixed surface, Journal of Combinatorial Theory Series B, v.87 n.1, p.38-71, January 2003 [doi>10.1016/S0095-8956(02)00027-8]
• 18: S. G. Williamson, Depth-First Search and Kuratowski Subgraphs, Journal of the ACM (JACM), v.31 n.4, p.681-693, Oct. 1984 [doi>10.1145/1634.322451]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms