ABSTRACT
It is well-known (Feige and Kilian [24], Håstad [39]) that approximating the chromatic number within a factor of n1-ε 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 Π2p-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 Kk-minors and graphs without odd Kk-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 Kk-minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-Kk-minors. Their time complexity is O(n3) and O(n4), 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 Kn/2,n/2 contains a Kk-minor for k ≤ n/2, but on the other hand, it does not contain an odd Kk-minor for any k ≥ 3. Odd K5-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 Kk-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(n3) 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 Kk-minor. Also, we shall give an O(n2500k) algorithm for deciding whether or not any 2500k-chromatic graph contains an odd-Kk-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.
- K. Appel and W. Haken. Every planar map is four colorable, part I. Discharging. Illinois J. Math., 21:429--490, 1977.]]Google ScholarCross Ref
- K. Appel, W. Haken, and J. Koch. Every planar map is four colorable, part II. Reducibility. Illinois J. Math., 21:491--567, 1977.]]Google ScholarCross Ref
- S. Arnborg and S. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math., 23:11--24, 1989.]] Google ScholarDigital Library
- M. Biro, M. Hujter, and Z. Tuza. Precoloring extension I, interval graphs. Discrete Math., 100:267--279, 1990.]] Google ScholarDigital Library
- 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.]]Google Scholar
- A. Blum and D. Karger. An Õ(n3/14)-coloring algorithm for 3-colorable graphs. Information Processing Letters, 61(1):49--53, 1997.]] Google ScholarDigital Library
- H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305--1317, 1996.]] Google ScholarDigital Library
- H. L. Bodlaender, K. Jansen, and G. J. Woeginger. Scheduling with incompatible jobs. Discrete Applied Math., 55:219--232, 1994.]] Google ScholarDigital Library
- T. Bohme, K. Kawarabayashi, J. Maharry, and B. Mohar. Linear connectivity forces large complete bipartite minors. To appear in J. Combin. Theory Ser B.]]Google Scholar
- B. Bollobas and A. Thomason. Highly linked graphs. Combinatorica, 16:313--320, 1996.]]Google ScholarCross Ref
- P. A. Catlin. A bound on the chromatic number of a graph. Discrete Math., 22:81--83, 1978.]]Google ScholarDigital Library
- M. Charikar and A. Sahai. Dimension reduction in the l1 norm. In Proceedings of the 43th Annual Symposium on Foundations of Computer Science (FOCS'02), pages 551--560, 2002.]] Google ScholarDigital Library
- G. Chartrand, D. Geller, and T. Hedetniemi. Graphs with forbidden subgraphs. J. Combin. Theory, 10:12--41, 1971.]]Google ScholarCross Ref
- G. Chartrand and H. V. Kronk. The point-arboricity of planar graphs. J. London Math. Soc., 44:612--616, 1969.]]Google ScholarCross Ref
- C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and S. Alistair. Embedding k-outerplanar graphs into '1. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pages 527--536, 2003.]] Google ScholarDigital Library
- Z.-Z. Chen. NC algorithms for partitioning sparse graphs into induced forests with an application. In Proc. 6th Internat. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 1004, Springer, Berlin, pages 428--437, 1995.]] Google ScholarDigital Library
- Z.-Z. Chen. Efficeint algorithms for acyclic coloring graphs. Theoretical Computer Scienece, 230:79--95, 2000.]] Google ScholarDigital Library
- Z.-Z. Chen and X. He. Parallen complexity of partitioning a planar graph into vertex-induced forests. Discrete Applied Math., 69:183--198, 1996.]] Google ScholarDigital Library
- 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.]]Google Scholar
- E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 637--646, Pittsburgh, PA, October 2005.]] Google ScholarDigital Library
- G. Ding, B. Oporowski, D. Sander, and D. Vertigan. Surface, tree-width, clique-minors, and partitions. J. Combin. Theory Ser. B, 79:221--246, 2000.]] Google ScholarDigital Library
- G. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85--92, 1952.]]Google ScholarCross Ref
- 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.]]Google Scholar
- U. Feige and J. Kilian. Zero-knowledge and the chromatic number. J. Comput. System Sci., 57:187--199, 1998.]] Google ScholarDigital Library
- M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35:727--739, 1988.]] Google ScholarDigital Library
- H. Gabow. Implementation of algorithms for maximum matching on non-bipartite graphs. Ph . D. Stanford University, Dep. Comput., 1973.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- J. Geelen, B. Gerards, L. Goddyn, B. Reed, P. Seymour, and A. Vetta. The odd case of Hadwiger's conjecture. Submitted.]]Google Scholar
- J. Geelen and B. Guenin. Packing odd circuits in eulerian graphs. J. Combin. Theory Ser. B, 86:280--295, 2002.]] Google ScholarDigital Library
- W. Goddard. Acyclic coloring of planar graphs. Discrete Math, 91:91--94, 1991.]] Google ScholarDigital Library
- M. Grotschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169--197, 1981.]]Google ScholarCross Ref
- M. Grotschel and W. Pullyblank. Weakly bipartite graphs and the max-cut problem. Oper. Res. Lett., 1:23--27, 1981.]]Google ScholarDigital Library
- B. Guenin. A characterization of weakly bipartite graphs. In Integer Programming and Combinatorial optimizaition, Proceedings, 6th IPCO conference, Houston, Texas, 1998, (R.E. Bixby et al., Eds), Lecture Notes in Computer Science, Springer-Verlag, Berlin, volume 1412, pages 9--22.]]Google Scholar
- B. Guenin. A characterization of weakly bipartite graphs. J. Combin. Theory Ser. B, 83:112--168, 2001.]] Google ScholarDigital Library
- B. Guenin. Talk at Oberwolfach on graph theory. Jan. 2005.]]Google Scholar
- A. Gupta, I. Newman, Y. Rabinovich, and S. Alistair. Cuts, trees and '1-embeddings of graphs. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99), pages 399--409, 1999.]] Google ScholarDigital Library
- S. Gutner. The complexity of planar graph choosability. Discrete Math., 159:119--130, 1996.]]Google ScholarCross Ref
- H. Hadwiger. Über eine Klassifikation der Streckenkomplexe. In Vierteljahrsschr. naturforsch. Ges. Zurich, volume 88, pages 133--142, 1943.]]Google Scholar
- J. Hastad. Clique is hard to approximate within n1??". Acta Math., 182:105--142, 1999.]]Google ScholarCross Ref
- M. Henzinger, S. Rao, and H. Gabow. Computing vertex connectivity: New bounds from old techniques. J. Algorithms, 34:222--250, 2000.]] Google ScholarDigital Library
- T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, 1995.]]Google Scholar
- K. Kawarabayashi. Linkage problem and its application to hadwiger's conjecture. preprint.]]Google Scholar
- K. Kawarabayashi. Minors in 7-chromatic graphs. Preprint.]]Google Scholar
- K. Kawarabayashi. On the connectivity of minimal counterexamples to Hadwiger's conjecture. To appear in J. Combin. Theory Ser. B.]] Google ScholarDigital Library
- K. Kawarabayashi, A. Kostochka, and G. Yu. On sufficient degree conditions for a graph to be k-linked. To appear in Combin. Probab. Comput.]] Google ScholarDigital Library
- K. Kawarabayashi and B. Mohar. Algorithmic aspects of Hadwiger's conjecture. Submitted.]]Google Scholar
- K. Kawarabayashi and B. Mohar. A relaxed Hadwiger's conjecture for list colorings. To appear in J. Combin. Theory Ser. B.]] Google ScholarDigital Library
- K. Kawarabayashi and B. Reed. Highly parity linked graphs. To appear in Combinatorica.]]Google Scholar
- K. Kawarabayashi and Z. Song. Some remarks on the odd hadwiger's conjecture. To appear in Combinatorica.]]Google Scholar
- K. Kawarabayashi and B. Toft. Any 7-chromatic graph has K7 or K4;4 as a minor. Combinatorica, 25:327--353, 2005.]] Google ScholarDigital Library
- K. Kawarabayashi and P. Wollan. Non-zero disjoint cycles in highly connected group-labelled graphs. J. Combin. Theory Ser. B, 96:296--301, 2006.]] Google ScholarDigital Library
- P. N. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC'93), pages 682--690, 1993.]] Google ScholarDigital Library
- A. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices (in Russian). Metody Diskret. Analiz., 38:37--58, 1982.]]Google Scholar
- A. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4:307--316, 1984.]]Google ScholarCross Ref
- E. Lawler. Combinatorial optimization; Networks and Matroids. Holt, Rinehart and Wilson, New York, 1976.]]Google Scholar
- W. Mader. Existenz n-fach zusammenhangender Teilgraphen in Graphen genugend grosser Kantendichte. Abh. Math. Sem. Univ. Hamburg, 37:86--97, 1972.]]Google ScholarCross Ref
- S. A. Plotkin, S. Rao, and W. D. Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), pages 462--470, 1994.]] Google ScholarDigital Library
- N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas. The four-color theorem. J. Combin. Theory Ser. B, 70:2--44, 1997.]] Google ScholarDigital Library
- N. Robertson and P. D. Seymour. Graph minors XIII. The disjoint paths problems. J. Combin. Theory Ser. B, 63:65--110, 1995.]] Google ScholarDigital Library
- N. Robertson and P. D. Seymour. Graph minors. XVII. Taming a vortex. J. Combin. Theory Ser. B, 77:162--210, 1999.]] Google ScholarDigital Library
- N. Robertson and P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B, 89:43--76, 2003.]] Google ScholarDigital Library
- N. Robertson, P. D. Seymour, and R. Thomas. Hadwiger's conjecture for K6-free graphs. Combinatorica, 13:279--361, 1993.]]Google ScholarCross Ref
- A. Roychoudhury and S. Sur-Kolay. Efficient algorithm for vertex arboricity of planar graphs. In Proc. 15th Internat. Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Springer, Berlin, volume 1026, pages 37--51, 1995.]] Google ScholarDigital Library
- A. Schrijver. A short proof of Guenin's characterization of weakly bipartite graphs. J. Combin. Theory Ser. B, 85:255--260, 2002.]] Google ScholarDigital Library
- P. D. Seymour. The matroids with the max-ow min-cut property. J. Combin. Theory Ser. B, 23:189--222, 1977.]]Google ScholarCross Ref
- R. Thomas and P. Wollan. An improved linear edge bound for graph linkages. Europ. J. Combin., 26:309--324, 2005.]] Google ScholarDigital Library
- A. Thomason. An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc., 95:261--265, 1984.]]Google ScholarCross Ref
- A. Thomason. The extremal function for complete minors. J. Combin. Theory Ser. B, 81:318--338, 2001.]] Google ScholarDigital Library
- C. Thomassen. Every planar graph is 5-choosable. J. Combin. Theory Ser. B, 62:180--181, 1994.]] Google ScholarDigital Library
- B. Toft. A survey of Hadwiger's conjecture. Congr. Numer., 115:249--283, 1996.]]Google Scholar
- Z. Tuza. Graph colorings with local constraints | a survey. Discuss. Math. Graph Theory, 17:161--228, 1997.]]Google ScholarCross Ref
- 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.]]Google Scholar
- M. Voigt. List colourings of planar graphs. Discrete Math., 120:215--219, 1993.]] Google ScholarDigital Library
- K. Wagner. Uber eine Eigenschaft der ebenen Komplexe. Math. Ann., 114:570--590, 1937.]]Google ScholarCross Ref
- 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.]]Google Scholar
Index Terms
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
Recommendations
Homomorphisms of triangle-free graphs without a K5-minor
In the course of extending Grotzsch's Theorem, we prove that every triangle-free graph without a K"5-minor is 3-colorable. It has been recently proved that every triangle-free planar graph admits a homomorphism to the Clebsch graph. We also extend this ...
List Colorings of K5-Minor-Free Graphs With Special List Assignments
The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L-list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? ...
Thomassen's Choosability Argument Revisited
Thomassen (J. Combin. Theory Ser. B, 62 (1994), pp. 180-181) proved that every planar graph is 5-choosable. This result was generalized by Škrekovski (Discrete Math., 190 (1998), pp. 223-226) and He, Miao, and Shen (Discrete Math., 308 (2008), pp. 4024-...
Comments