Additive approximation algorithms for list-coloring minor-closed class of graphs

ABSTRACT

It is known that computing the list chromatic number is harder than computing the chromatic number (assuming NP ≠ coNP). In fact, the problem of deciding whether a given graph is f-list-colorable for a function f: V → {c -1, c} for c ≥ 3 is Π^p₂-complete. In general, it is believed that approximating list coloring is hard for dense graphs.

In this paper, we are interested in sparse graphs. More specifically, we deal with nontrivial minor-closed classes of graphs, i.e., graphs excluding some K_k minor. We refine the seminal structure theorem of Robertson and Seymour, and then give an additive approximation for list-coloring within k - 2 of the list chromatic number. This improves the previous multiplicative O(k)-approximation algorithm [20]. Clearly our result also yields an additive approximation algorithm for graph coloring in a minor-closed graph class. This result may give better graph colorings than the previous multiplicative 2-approximation algorithm for graph coloring in a minor-closed graph class [6].

Our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected H-minor-free graphs. In particular, this class of graphs can be easily decomposed into two parts so that one part has bounded treewidth and the other part is a disjoint union of bounded-genus graphs. Moreover, we can control the number of edges between the two parts. The proof method itself tells us how knowledge of a local structure can be used to gain a global structure, which gives new insight on how to decompose a graph with the help of local-structure information.

REFERENCES

• 1: Noga Alon, Restricted colorings of graphs, Surveys in combinatorics, 1993, Cambridge University Press, New York, NY, 1993
• 2: K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois Journal of Mathematics, 21 (1977), pp. 429--490.
• 3: K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois Journal of Mathematics, 21 (1977), pp. 491--567.
• 4: Sanjeev Arora , Eden Chlamtac, New approximation guarantee for chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132548]
• 5: Erik D. Demaine , Mohammadtaghi Hajiaghayi, Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, v.28 n.1, p.19-36, January 2008 [doi>10.1007/s00493-008-2140-4]
• 6: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Ken-ichi Kawarabayashi, Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.637-646, October 23-25, 2005 [doi>10.1109/SFCS.2005.14]
• 7: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Naomi Nishimura , Prabhakar Ragde , Dimitrios M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, v.69 n.2, p.166-166, September 2004 [doi>10.1016/j.jcss.2003.12.001]
• 8: Matt DeVos , Ken-ichi Kawarabayashi , Bojan Mohar, Locally planar graphs are 5-choosable, Journal of Combinatorial Theory Series B, v.98 n.6, p.1215-1232, November, 2008 [doi>10.1016/j.jctb.2008.01.003]
• 9: Reinhard Diestel , Tommy R. Jensen , Konstantin Yu. Gorbunov , Carsten Thomassen, Highly connected sets and the excluded grid theorem, Journal of Combinatorial Theory Series B, v.75 n.1, p.61-73, Jan. 1999 [doi>10.1006/jctb.1998.1862]
• 10: G. A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 85--92.
• 11: P. Erdős, Rubin and Taylor, Choosability in graphs. Proc. West-Coast conference on Combinatorics, Graph Theory and Computing, Arcata Califonia, Congressus Numerantium XXVI (1979) 125--157.
• 12: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 13: S. Gutner, The complexity of planar graph choosability. Discrete Math. 159 (1996), 119--130.
• 14: H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich, 88 (1943), pp. 133--142.
• 15: J. Håstad, Clique is hard to approximate within n^1-ε, Acta Math. 182 (1999), 105--142.
• 16: David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998 [doi>10.1145/274787.274791]
• 17: K. Kawarabayashi, Minors in 7-chromatic graphs, preprint.
• 18: Ken-Ichi Kawarabayashi, Approximating List-Coloring on a Fixed Surface, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_28]
• 19: Ken-ichi Kawarabayashi , Bjarne Toft†, Any 7-Chromatic Graphs Has K ₇ Or K _4,4 As A Minor, Combinatorica, v.25 n.3, p.327-353, May 2005 [doi>10.1007/s00493-005-0019-1]
• 20: Ken-ichi Kawarabayashi , Bojan Mohar, Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132576]
• 21: K. Kawarabayashi and B. Mohar, List-color-critical graphs on a fixed surface, submitted.
• 22: A. V. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica, 4 (1984), pp. 307--316.
• 23: B. Reed, Tree width and tangles: a new connectivity measure and some applications, in Surveys in combinatorics, 1997 (London), vol. 241 of London Math. Soc. Lecture Note Ser., Cambridge Univ. Press, Cambridge, 1997, pp. 87--162.
• 24: 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]
• 25: N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, 7 (1986), pp. 309--322.
• 26: Neil Robertson , P. D. Seymour, Graph minors. XI.: circuits on a surface, Journal of Combinatorial Theory Series B, v.60 n.1, p.72-106, Jan. 1994 [doi>10.1006/jctb.1994.1007]
• 27: Neil Robertson , P. D. Seymour, Graph minors. XII: distance on a surface, Journal of Combinatorial Theory Series B, v.64 n.2, p.240-272, July 1995 [doi>10.1006/jctb.1995.1034]
• 28: Neil Robertson , P. D. Seymour, Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory Series B, v.89 n.1, p.43-76, September 2003 [doi>10.1016/S0095-8956(03)00042-X]
• 29: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
• 30: N. Robertson, P. Seymour, and R. Thomas, Hadwiger's conjecture for K6-free graphs, Combinatorica, 13 (1993), pp. 279--361.
• 31: Andrew Thomason, The extremal function for complete minors, Journal of Combinatorial Theory Series B, v.81 n.2, p.318-338, March 2001 [doi>10.1006/jctb.2000.2013]
• 32: Carsten Thomassen, Every planar graph is 5-choosable, Journal of Combinatorial Theory Series B, v.62 n.1, p.180-181, Sept. 1994 [doi>10.1006/jctb.1994.1062]
• 33: 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]
• 34: Z. Tuza, Graph colorings with local constraints---a survey. Discuss. Math. Graph Theory 17 (1997), 161--228.
• 35: K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570--590.
• 36: Margit Voigt, List colourings of planar graphs, Discrete Mathematics, v.120 n.1-3, p.215-219, Sept. 1993 [doi>10.1016/0012-365X(93)90579-I]
• 37: Vizing, Coloring the vertices of a graph in prescribed colors. Metpdy Diskret. Anal. v Teorii Kodov i Schem 29 (1976) 3--10. (In Russian)

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.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

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