Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs

ABSTRACT

It is well-known (Feige and Kilian [24], Håstad [39]) that approximating the chromatic number within a factor of n^1-ε cannot be done in polynomial time for ε>0, unless coRP = NP. Computing the list-chromatic number is much harder than determining the chromatic number. It is known that the problem of deciding if the list-chromatic number is k, where k ≥ 3, is Π₂^p-complete [37].In this paper, we focus on minor-closed and odd-minor-closed families of graphs. In doing that, we may as well consider only graphs without K_k-minors and graphs without odd K_k-minors for a fixed value of k, respectively. Our main results are that there is a polynomial time approximation algorithm for the list-chromatic number of graphs without K_k-minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-K_k-minors. Their time complexity is O(n³) and O(n⁴), respectively. The algorithms have multiplicative error O(√log k) and additive error O(k), and the multiplicative error occurs only for graphs whose list-chromatic number and chromatic number are Θ(k), respectively.Let us recall that H has an odd complete minor of order l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Let us observe that the complete bipartite graph K_n/2,n/2 contains a K_k-minor for k ≤ n/2, but on the other hand, it does not contain an odd K_k-minor for any k ≥ 3. Odd K₅-minor-free graphs are closely related to one field of discrete optimization which is finding conditions under which a given polyhedron has integer vertices, so that integer optimization problems can be solved as linear programs. See [33, 34, 64]. Also, the odd version of the well-known Hadwiger's conjecture has been considered, see [28].Our main idea involves precoloring extension. This idea is used in many results; one example is Thomassen's proof on his celebrated theorem on planar graphs [69].The best previously known approximation for the first result is a simple O(k √log k)-approximation following algorithm that guarantees a list-coloring with O(k √log k) colors for K_k-minor-free graphs. This follows from results of Kostochka [54, 53] and Thomason [67, 68].The best previous approximation for the second result comes from the recent result of Geelen et al. [28] who gave an O(k √log k)-approximation algorithm.We also relate our algorithm to the well-known conjecture of Hadwiger [38] and its odd version. In fact, we give an O(n³) algorithm to decide whether or not a weaker version of Hadwiger's conjecture is true. Here, by a weaker version of Hadwiger's conjecture, we mean a conjecture which says that any 27k-chromatic graph contains a K_k-minor. Also, we shall give an O(n^2500k) algorithm for deciding whether or not any 2500k-chromatic graph contains an odd-K_k-minor.Let us mention that this presentation consists of two papers which are merged into this one. The first one consists of results concerning minor-closed classes of graphs by two current authors, and the other consists of results concerning odd-minor-closed classes of graphs by the first author.

REFERENCES

• 1: K. Appel and W. Haken. Every planar map is four colorable, part I. Discharging. Illinois J. Math., 21:429--490, 1977.
• 2: K. Appel, W. Haken, and J. Koch. Every planar map is four colorable, part II. Reducibility. Illinois J. Math., 21:491--567, 1977.
• 3: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 4: M. Biró , M. Hujter , Zs. Tuza, Precoloring extension. I: Interval graphs, Discrete Mathematics, v.100 n.1-3, p.267-279, May 15, 1992 [doi>10.1016/0012-365X(92)90646-W]
• 5: M. Biro, M. Hujter, and Z. Tuza. Cross fertilisation of graph theory and aircraft maintenace scheduling. In Thirty-Second Annual Symposium (G. Davison, ed.), AGIFORS (Airline Group of the international Federation of Operational Research), pages 307--317, 1993.
• 6: Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
• 7: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 8: Hans L. Bodlaender , Klaus Jansen , Gerhard J. Woeginger, Scheduling with incompatible jobs, Discrete Applied Mathematics, v.55 n.3, p.219-232, Dec. 13, 1994 [doi>10.1016/0166-218X(94)90009-4]
• 9: T. Bohme, K. Kawarabayashi, J. Maharry, and B. Mohar. Linear connectivity forces large complete bipartite minors. To appear in J. Combin. Theory Ser B.
• 10: B. Bollobas and A. Thomason. Highly linked graphs. Combinatorica, 16:313--320, 1996.
• 11: P. A. Catlin. A bound on the chromatic number of a graph. Discrete Math., 22:81--83, 1978.
• 12: Moses Charikar , Amit Sahai, Dimension Reduction in the \ell _1 Norm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.551-560, November 16-19, 2002
• 13: G. Chartrand, D. Geller, and T. Hedetniemi. Graphs with forbidden subgraphs. J. Combin. Theory, 10:12--41, 1971.
• 14: G. Chartrand and H. V. Kronk. The point-arboricity of planar graphs. J. London Math. Soc., 44:612--616, 1969.
• 15: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 16: Zhi-Zhong Chen, NC Algorithms for Partitioning Sparse Graphs into Induced Forests with an Application, Proceedings of the 6th International Symposium on Algorithms and Computation, p.428-437, December 04-06, 1995
• 17: Zhi-Zhong Chen, Efficient algorithms for acyclic colorings of graphs, Theoretical Computer Science, v.230 n.1-2, p.75-95, Jan. 2000 [doi>10.1016/S0304-3975(97)00254-5]
• 18: Zhi-Zhong Chen , Xin He, Parallel complexity of partitioning a planar graph into vertex-induced forests, Discrete Applied Mathematics, v.69 n.1-2, p.183-198, Aug. 13, 1996 [doi>10.1016/0166-218X(96)00089-3]
• 19: W. Cunningham and A. Marsh. A primal algorithm for optimum matching. In Polyhedral Combinatorics, (dedicated to the memory of D. R. Fulkerson), Eds: M. L. Balinski and A. J. Hoffman, Math. Programming Sud. No. 8, North-Holland, Amsterdam, pages 60--72, 1978.
• 20: 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]
• 21: Guoli Ding , Bogdan Oporowski , Daniel P. Sanders , Dirk Vertigan, Surfaces, tree-width, clique-minors, and partitions, Journal of Combinatorial Theory Series B, v.79 n.2, p.221-246, July 2000 [doi>10.1006/jctb.2000.1962]
• 22: G. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85--92, 1952.
• 23: P. Erdos, Rubin, and Taylor. Choosability in graphs. In Proc. West-Coast conference on Combinatorics Graph Theory and Computing, Arcata Califonia, Congressus Numerantium, volume XXVI, pages 125--157, 1979.
• 24: 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]
• 25: Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
• 26: Harold Neil Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs., 1974
• 27: Z. Galil, S. Micali, and H. Gabow. Priority queues with variable priority and an o(ev log v) algorithm for finding a maximal weighted matching in general graohs. In 23rd Annual Sumposium on Foundations of Computer Science (Chicago), pages 255--261, 1982.
• 28: J. Geelen, B. Gerards, L. Goddyn, B. Reed, P. Seymour, and A. Vetta. The odd case of Hadwiger's conjecture. Submitted.
• 29: James F. Geelen , Bertrand Guenin, Packing odd circuits in Eulerian graphs, Journal of Combinatorial Theory Series B, v.86 n.2, p.280-295, November 2002 [doi>10.1006/jctb.2002.2128]
• 30: Wayne Goddard, Acyclic colorings of planar graphs, Discrete Mathematics, v.91 n.1, p.91-94, Aug. 7 1991 [doi>10.1016/0012-365X(91)90166-Y]
• 31: M. Grotschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169--197, 1981.
• 32: M. Grotschel and W. Pullyblank. Weakly bipartite graphs and the max-cut problem. Oper. Res. Lett., 1:23--27, 1981.
• 33: Bertrand Guenin, A Characterization of Weakly Bipartite Graphs, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.9-22, June 22-24, 1998
• 34: Bertrand Guenin, A characterization of weakly bipartite graphs, Journal of Combinatorial Theory Series B, v.83 n.1, p.112-168, September 2001 [doi>10.1006/jctb.2001.2051]
• 35: B. Guenin. Talk at Oberwolfach on graph theory. Jan. 2005.
• 36: Anupam Gupta , Alistair Sinclair , Ilan Newman , Yuri Rabinovich, Cuts, Trees and -Embeddings of Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.399, October 17-18, 1999
• 37: S. Gutner. The complexity of planar graph choosability. Discrete Math., 159:119--130, 1996.
• 38: H. Hadwiger. Uber eine Klassifikation der Streckenkomplexe. In Vierteljahrsschr. naturforsch. Ges. Zurich, volume 88, pages 133--142, 1943.
• 39: J. Hastad. Clique is hard to approximate within n1??". Acta Math., 182:105--142, 1999.
• 40: Monika R. Henzinger , Satish Rao , Harold N. Gabow, Computing vertex connectivity: new bounds from old techniques, Journal of Algorithms, v.34 n.2, p.222-250, Feb. 2000 [doi>10.1006/jagm.1999.1055]
• 41: T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, 1995.
• 42: K. Kawarabayashi. Linkage problem and its application to hadwiger's conjecture. preprint.
• 43: K. Kawarabayashi. Minors in 7-chromatic graphs. Preprint.
• 44: K. Kawarabayashi. On the connectivity of minimal counterexamples to Hadwiger's conjecture. To appear in J. Combin. Theory Ser. B.
• 45: K. Kawarabayashi, A. Kostochka, and G. Yu. On sufficient degree conditions for a graph to be k-linked. To appear in Combin. Probab. Comput.
• 46: K. Kawarabayashi and B. Mohar. Algorithmic aspects of Hadwiger's conjecture. Submitted.
• 47: K. Kawarabayashi and B. Mohar. A relaxed Hadwiger's conjecture for list colorings. To appear in J. Combin. Theory Ser. B.
• 48: K. Kawarabayashi and B. Reed. Highly parity linked graphs. To appear in Combinatorica.
• 49: K. Kawarabayashi and Z. Song. Some remarks on the odd hadwiger's conjecture. To appear in Combinatorica.
• 50: 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]
• 51: K. Kawarabayashi and P. Wollan. Non-zero disjoint cycles in highly connected group-labelled graphs. J. Combin. Theory Ser. B, 96:296--301, 2006.
• 52: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 53: A. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices (in Russian). Metody Diskret. Analiz., 38:37--58, 1982.
• 54: A. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4:307--316, 1984.
• 55: E. Lawler. Combinatorial optimization; Networks and Matroids. Holt, Rinehart and Wilson, New York, 1976.
• 56: W. Mader. Existenz n-fach zusammenhangender Teilgraphen in Graphen genugend grosser Kantendichte. Abh. Math. Sem. Univ. Hamburg, 37:86--97, 1972.
• 57: Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
• 58: 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]
• 59: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 60: Neil Robertson , P. D. Seymour, Graph minors, Journal of Combinatorial Theory Series B, v.77 n.1, p.162-210, Sept. 1999 [doi>10.1006/jctb.1999.1919]
• 61: 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]
• 62: N. Robertson, P. D. Seymour, and R. Thomas. Hadwiger's conjecture for K6-free graphs. Combinatorica, 13:279--361, 1993.
• 63: Abhik Roychoudhury , Susmita Sur-Kolay, Efficient Algorithms for Vertex Arboricity of Planar Graphs, Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science, p.37-51, December 18-20, 1995
• 64: Alexander Schrijver, A short proof of Guenin's characterization of weakly bipartite graphs, Journal of Combinatorial Theory Series B, v.85 n.2, p.255-260, July 2002 [doi>10.1006/jctb.2001.2101]
• 65: P. D. Seymour. The matroids with the max-ow min-cut property. J. Combin. Theory Ser. B, 23:189--222, 1977.
• 66: Robin Thomas , Paul Wollan, An improved linear edge bound for graph linkages, European Journal of Combinatorics, v.26 n.3-4, p.309-324, April-May 2005 [doi>10.1016/j.ejc.2004.02.013]
• 67: A. Thomason. An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc., 95:261--265, 1984.
• 68: 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]
• 69: 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]
• 70: B. Toft. A survey of Hadwiger's conjecture. Congr. Numer., 115:249--283, 1996.
• 71: Z. Tuza. Graph colorings with local constraints | a survey. Discuss. Math. Graph Theory, 17:161--228, 1997.
• 72: V. G. Vizing. Coloring the vertices of a graph in prescribed colors. Metody Diskret. Anal. v Teorii Kodov i Schem (In Russian), 29:3--10, 1976.
• 73: 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]
• 74: K. Wagner. Uber eine Eigenschaft der ebenen Komplexe. Math. Ann., 114:570--590, 1937.
• 75: D. R. Woodall. Improper colourings of graphs. In Graph Colourings (ed. R. Nelson and R. J. Wilson), Pitman Research Notes, Longman, volume 218, pages 45--63, 1990.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Theory

Keywords:
Hadwiger conjecture, graph coloring, graph minor, list coloring, odd-minor