Coloring triangle-free graphs on surfaces

ABSTRACT

Gimbel and Thomassen asked whether 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for every surface which combined with previous results gives a lineartime algorithm to compute the chromatic number of such graphs.

Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface Σ guarantees the existence of a subgraph H, whose size depends only on Σ, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the "winding number" of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends to find a 3-coloring.

If the input triangle-free graph G drawn in Σ is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates Σ then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.

REFERENCES

• 1: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 2: Sergio Cabello , Bojan Mohar, Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs, Discrete & Computational Geometry, v.37 n.2, p.213-235, February 2007 [doi>10.1007/s00454-006-1292-5]
• 3: Zdeněk Dvořák , Ken-ichi Kawarabayashi , Robin Thomas, Three-coloring triangle-free planar graphs in linear time, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1176-1182, January 04-06, 2009, New York, New York
• 4: D. Eppstein, Subgraph isomorphism in planar graphs and related problems, J. Algor. and Appl., 3 (1999), pp. 1--27.
• 5: S. Fisk, The nonexistence of colorings, J. Combin. Theory Ser. B, 24 (1978), pp. 247--248.
• 6: T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hungar. Acad. Sci., 8 (1963), pp. 165--192.
• 7: T. Gallai, Kritische Graphen II, Publ. Math. Inst. Hungar. Acad. Sci., 8 (1963), pp. 373--395.
• 8: 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
• 9: J. Gimbel and C. Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc., 349 (1997), pp. 4555--4564.
• 10: H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 8 (1959), pp. 109--120.
• 11: Joan P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, Journal of Combinatorial Theory Series B, v.65 n.1, p.139-155, Sept. 1995 [doi>10.1006/jctb.1995.1047]
• 12: P. J. Heawood, Map-color theorem, Quart. J. Pure Appl. Math., 24 (1890), pp. 332--338.
• 13: Yusuke Kobayashi , Ken-ichi Kawarabayashi, Algorithms for finding an induced cycle in planar graphs and bounded genus graphs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1146-1155, January 04-06, 2009, New York, New York
• 14: Ł. Kowalik, Fast 3-coloring triangle-free planar graphs, ESA 2004, Lecture Notes in Comput. Sci., 3221 (2004), pp. 436--447.
• 15: Lukasz Kowalik , Maciej Kurowski, Short path queries in planar graphs in constant time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780565]
• 16: Bojan Mohar , Paul D. Seymour, Coloring locally bipartite graphs on surfaces, Journal of Combinatorial Theory Series B, v.84 n.2, p.301-310, March 2002 [doi>10.1006/jctb.2001.2086]
• 17: B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, Baltimore, MD, 2001.
• 18: A. Nakamoto, S. Negami and K. Ota, Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces, Discrete Math., 285 (2004), pp. 211--218.
• 19: Jaroslav Nešetřil , Patrice Ossona de Mendez, Linear time low tree-width partitions and algorithmic consequences, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132575]
• 20: Jaroslav Nešetřil , Patrice Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics, v.29 n.3, p.760-776, April, 2008 [doi>10.1016/j.ejc.2006.07.013]
• 21: Jaroslav Nešetřil , Patrice Ossona de Mendez, Grad and classes with bounded expansion II. Algorithmic aspects, European Journal of Combinatorics, v.29 n.3, p.777-791, April, 2008 [doi>10.1016/j.ejc.2006.07.014]
• 22: Bruce Reed, Rooted routing in the plane, Discrete Applied Mathematics, v.57 n.2-3, p.213-227, Feb. 24, 1995 [doi>10.1016/0166-218X(94)00104-L]
• 23: B. A. Reed, N. Robertson, A. Schrijver and P. D. Seymour, Finding disjoint trees in planar graphs in linear time, Contemp. Math., 147 (1993), pp. 295--301.
• 24: G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.
• 25: G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A., 60 (1968), pp. 438--445.
• 26: Neil Robertson , P D Seymour, Graph minors. VI. Disjoint paths across a disc, Journal of Combinatorial Theory Series B, v.41 n.1, p.115-138, Aug. 1986 [doi>10.1016/0095-8956(86)90031-6]
• 27: 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]
• 28: H. Suzuki, T. Akama and T. Nishiseki, An algorithm for fidning a forest in a planar graph---case in which a net may have terminals on the two specified face boundaries, Electron. Comm. Japan Part III Fund Electron. Sci, 72 (1989), pp. 68--79.
• 29: 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]
• 30: Carsten Thomassen, Color-critical graphs on a fixed surface, Journal of Combinatorial Theory Series B, v.70 n.1, p.67-100, May 1997 [doi>10.1006/jctb.1996.1722]
• 31: 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]
• 32: D. A. Youngs, 4-chromatic projective graphs, Journal of Graph Theory, v.21 n.2, p.219-227, Feb. 1996 [doi>10.1002/(SICI)1097-0118(199602)21:2<219::AID-JGT12>3.0.CO;2-E]

INDEX TERMS

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

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