{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:28Z","timestamp":1773704788264,"version":"3.50.1"},"reference-count":196,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,2,1]],"date-time":"2007-02-01T00:00:00Z","timestamp":1170288000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2007,2]]},"DOI":"10.1007\/s00373-006-0684-x","type":"journal-article","created":{"date-parts":[[2007,2,22]],"date-time":"2007-02-22T17:15:01Z","timestamp":1172164501000},"page":"1-46","source":"Crossref","is-referenced-by-count":25,"title":["Some Recent Progress and Applications in Graph Minor Theory"],"prefix":"10.1007","volume":"23","author":[{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"684_CR1","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for non-planar graphs, J. Amer. Math. Soc. 3, 801\u2013809 (1990)"},{"key":"684_CR2","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable, Part I. Discharging, Illinois J. Math. 21, 429\u2013490 (1977)"},{"key":"684_CR3","unstructured":"Appel, K., Haken, W., Koch, J.: Every planar map is four colorable, Part II. Reducibility, Illinois J. Math. 21, 491\u2013567 (1977)"},{"key":"684_CR4","doi-asserted-by":"crossref","unstructured":"Archdeacon, D.: A Kuratowski theorem for the projective plane, J. Graph Theory 5, 243\u2013246 (1981)","DOI":"10.1002\/jgt.3190050305"},{"key":"684_CR5","unstructured":"Archdeacon, D., Huneke, P.: A Kuratowski theorem for nonorientable surfaces, J. Combin. Theory, Ser. B 46, 173\u2013231 (1989)"},{"key":"684_CR6","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math. 23, 11\u201324 (1989)"},{"key":"684_CR7","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs, J. Assoc. Comput. Mach. 41, 153\u2013180 (1994)"},{"key":"684_CR8","unstructured":"Blum, A., Karger, D.: An O(n3\/14)-coloring algorithm for 3-colorable graphs, Inform. Proc. Lett. 61, 49\u201353 (1997)"},{"key":"684_CR9","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decomposition of small treewidth, SIAM J. Comput. 25, 1305\u20131317 (1996)"},{"key":"684_CR10","unstructured":"B\u00f6hme, T., Kawarabayashi, K., Maharry, J., Mohar, B.: Linear connectivity forces large complete bipartite minors, to appear."},{"key":"684_CR11","unstructured":"B\u00f6hme, T., Kawarabayashi, K., Maharry, J., Mohar, B.: K3,k-minors in large 7-connected graphs, submitted."},{"key":"684_CR12","doi-asserted-by":"crossref","unstructured":"B\u00f6hme, T., Kostochka, A.: Disjoint Kr-minors in large graphs with given average degree, Europ. J. Combinatorics 26, 289\u2013292 (2005)","DOI":"10.1016\/j.ejc.2003.12.017"},{"key":"684_CR13","unstructured":"B\u00f6hme, T., Maharry, J., Mohar, B.: Ka,k minors in graphs of bounded tree-width, J. Combin. Theory, Ser. B 86, 133\u2013147 (2002)"},{"key":"684_CR14","unstructured":"B\u00f6hme, T., Mohar, B., Reed, B.: Forced minors in tough graphs, submitted."},{"key":"684_CR15","unstructured":"Bollob\u00e1s, B., Thomason, A.: Highly linked graphs, Combinatorica 16, 313\u2013320 (1996)"},{"key":"684_CR16","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B., Thomason, A.: Proof of a conjecture of Mader, Erd\u0151s and Hajnal on topological complete subgraphs, European J. Combin. 19, 883\u2013887 (1998)","DOI":"10.1006\/eujc.1997.0188"},{"key":"684_CR17","unstructured":"Brunet, R., Mohar, B., Richter, R.B.: Separating and nonseparating disjoint homotopic cycles in graph embeddings, J. Comb. Theory, Ser. B 66, 201\u2013231 (1996)"},{"key":"684_CR18","unstructured":"Chartrand, G., Kronk, H.V.: The point-arboricity of planar graphs, J. London Math. Soc. 44, 612\u2013616 (1969)"},{"key":"684_CR19","unstructured":"Chartrand, G., Geller, D.P., Hedetniemi, T.: Graphs with forbidden subgraphs, J. Combin. Theory 10, 12\u201341 (1971)"},{"key":"684_CR20","unstructured":"Chen, Z.-Z.: 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, 1995, pp. 428\u2013437."},{"key":"684_CR21","unstructured":"Chen, Z.-Z., He, X.: Parallel complexity of partitioning a planar graph into vertex-induced forests, Discrete Appl. Math. 69, 183\u2013198 (1996)"},{"key":"684_CR22","unstructured":"Chen, Z.-Z.: Efficient algorithms for acyclic coloring graphs, Theor. Comp. Sci. 230, 79\u201395 (2000)"},{"key":"684_CR23","doi-asserted-by":"crossref","unstructured":"Chen, G., Gould, R., Kawarabayashi, K., Pfender, F., Wei, B.: Graph minors and linkage problem I, J. Graph Theory 49, 75\u201391 (2005)","DOI":"10.1002\/jgt.20067"},{"key":"684_CR24","unstructured":"Colin de Verdi\u00e8re, Y.: Sur un nouvel invariant des graphes et un crit\u00e8re de planarit\u00e9, J. Comb. Theory, Ser. B 50, 11\u201321 (1990)"},{"key":"684_CR25","unstructured":"Colin de Verdi\u00e8re, Y.: Multiplicities of eigenvalues and tree-width of graphs, J. Comb. Theory, Ser. B 74, 121\u2013146 (1998)"},{"key":"684_CR26","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, Y.: On a new graph invariant and a criterion of planarity, in Graph Structure Theory, N. Robertson and P. Seymour, editors, Contemp. Math. 147, pp. 137\u2013147, Amer. Math. Soc., Providence, RI, 1993.","DOI":"10.1090\/conm\/147\/01168"},{"key":"684_CR27","doi-asserted-by":"crossref","unstructured":"Conway, J., Gordon, C.: Knots and links in spatial graphs, J. Graph Theory 7, 445\u2013453 (1983)","DOI":"10.1002\/jgt.3190070410"},{"key":"684_CR28","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Fomin, F., Hajiaghayi, M., Thilikos, D.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, J. ACM 52, 1\u201329 (2005)","DOI":"10.1145\/1101821.1101823"},{"key":"684_CR29","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.: Fast algorithms for hard graph problems: Bidimensionality, minors and local tree-width, Proc. 12th Internat. Symp. on Graph Drawing, Lecture Notes in Computer Science 3383, Springer, 2004, pp. 517\u2013533.","DOI":"10.1007\/978-3-540-31843-9_57"},{"key":"684_CR30","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation and coloring, Proc. 46th Ann. IEEE Symp. Found. Comp. Sci., Pittsburgh, PA, 2005, pp. 637\u2013646.","DOI":"10.1109\/SFCS.2005.14"},{"key":"684_CR31","unstructured":"Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition, preprint, 2006."},{"key":"684_CR32","unstructured":"DeVos, M., Ding, G., Oporowski, B., Sanders, D., Reed, B., Seymour, P., Vertigan, D.: Excluding any graph as a minor allows a low tree-width 2-coloring. J. Combin. Theory Ser. B 91, 25\u201341 (2004)"},{"key":"684_CR33","unstructured":"DeVos, M., Goddyn, L., Mohar, B., Vertigan, D., Zhu, X.: Coloring-flow duality of embedded graphs, Trans. Amer. Math. Soc. 357, 3993\u20134016 (2005)"},{"key":"684_CR34","unstructured":"DeVos, M., Hedge, R., Kawarabayashi, K., Norine, S., Thomas, R., Wollan, P.: Large 6-connected graphs without K6-minors, preprint."},{"key":"684_CR35","unstructured":"DeVos, M., Kawarabayashi, K.-I., Mohar, B.: 5-choosability of locally planar graphs, preprint, 2006."},{"key":"684_CR36","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Decompositions \u2013 A Study in Infinite Graph Theory, Oxford University Press, Oxford, 1990.","DOI":"10.1093\/oso\/9780198532101.001.0001"},{"key":"684_CR37","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 3rd Edition, Springer, 2005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"684_CR38","unstructured":"Diestel, R.: The depth-first search tree structure of T-free graphs, J. Combin. Theory Ser. B 61, 260\u2013262 (1994)"},{"key":"684_CR39","unstructured":"Diestel, R., Rempel, C.: Dense minors in graphs of large girth, Combinatorica 25, 111\u2013116 (2005)"},{"key":"684_CR40","unstructured":"Diestel, R., Yu. Gorbunov, K., Jensen, T.R., Thomassen, C.: Highly connected sets and the excluded grid theorem, J. Combin. Theory Ser. B 75, 61\u201373 (1999)"},{"key":"684_CR41","unstructured":"Diestel, R., Thomas, R.: Excluding a countable clique, J. Combin. Theory Ser. B 76, 41\u201367 (1999)"},{"key":"684_CR42","unstructured":"Ding, G.:private communication."},{"key":"684_CR43","unstructured":"Ding, G., Oporowski, B., Sanders, D.P., Vertigan, D.: Surface, tree-width, clique-minors, and partitions, J. Combin. Theory Ser. B 79, 221\u2013246 (2000)"},{"key":"684_CR44","unstructured":"Dirac, G.A.: A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27, 85\u201392 (1952)"},{"key":"684_CR45","unstructured":"Dirac, G.A.: Trennende Knotenpunktmengen und Reduzibilit\u00e4t abstrakter Graphen mit Anwendung auf das Vierfarbenproblem, J. reine angew. Math. 204, 116\u2013131 (1960)"},{"key":"684_CR46","doi-asserted-by":"crossref","unstructured":"Dirac, G.A.: On the structure of 5- and 6-chromatic abstract graphs, J. reine angew. Math. 214\/215, 43\u201352 (1964)","DOI":"10.1515\/crll.1964.214-215.43"},{"key":"684_CR47","doi-asserted-by":"crossref","unstructured":"Ellingham, M.N., Zha, X.: Separating cycles in doubly toroidal embeddings, Graphs Combin. 19, 161\u2013175 (2003)","DOI":"10.1007\/s00373-002-0491-y"},{"key":"684_CR48","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families, Algorithmica 27, 275\u2013291 (2000)"},{"key":"684_CR49","unstructured":"Erd\u0151s, P., P\u00f3sa, L.: On independet circuits contained in a graph, Canad. J. Math. 17, 347\u2013352 (1965)"},{"key":"684_CR50","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry, Compositio Math. 2 , 463\u2013470 (1935)"},{"key":"684_CR51","unstructured":"Erd\u0151s, P., Rubin, A., Taylor, H.: Choosability in graphs, in Proc. West-Coast Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XXVI, 125\u2013157 (1979)"},{"key":"684_CR52","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: Zero-knowledge and the chromatic number, J. Comput. System Sci. 57, 187\u2013199 (1998)","DOI":"10.1006\/jcss.1998.1587"},{"key":"684_CR53","doi-asserted-by":"crossref","unstructured":"Foisy, J.: A newly recognized intrinsically knotted graph, J. Graph Theory 43, 199\u2013209 (2003)","DOI":"10.1002\/jgt.10114"},{"key":"684_CR54","unstructured":"Fortune, S., Hopcroft, J.E., Wylie, J.: The directed subgraph homeomorphism problem, Theor. Comput. Sci. 10, 111\u2013121 (1980)"},{"key":"684_CR55","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Branch-width and well-quasi-ordering in matroids and graphs, J. Combin. Theory Ser. B 84, 270\u2013290 (2002)"},{"key":"684_CR56","unstructured":"Geelen, J.F., Whittle, G.: Branch-width and Rota's conjecture, J. Combin. Theory Ser. B 86, 315\u2013330 (2002)"},{"key":"684_CR57","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Disjoint cocircuits in matroids with large rank, J. Combin. Theory Ser. B 87, 270\u2013279 (2003)"},{"key":"684_CR58","unstructured":"Geelen, J.F., Whittle, G.: Cliques in dense GF(q)-representable matroids, J. Combin. Theory Ser. B 87, 264\u2013269 (2003)"},{"key":"684_CR59","unstructured":"Geelen, J.F., Gerards, A.M.H., Robertson, N., Whittle, G.: On the excluded minors for the matroids of branch-width k, J. Combin. Theory Ser. B 88, 261\u2013265 (2003)"},{"key":"684_CR60","unstructured":"Geelen, J.F., Gerards, A.M.H., Robertson, N., Whittle, G.: Obstructions to branch-decomposition of matroids, to appear in J. Combin. Theory Ser. B."},{"key":"684_CR61","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Excluding a planar graph from GF(q)-representable matroids, preprint."},{"key":"684_CR62","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: On Rota's Conjecture and excluded minors containing large projective geometries, to appear in J. Combin. Theory Ser. B."},{"key":"684_CR63","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Tangles, tree-decompositions, and grids in matroids, preprint."},{"key":"684_CR64","doi-asserted-by":"crossref","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Towards a structure theory for matrices and matroids, to appear in Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006. European Mathematical Society, 2006.","DOI":"10.4171\/022-3\/41"},{"key":"684_CR65","doi-asserted-by":"crossref","unstructured":"Geelen, J.F., Gerards, A.M.H., Whittle, G.: Towards a matroid-minor structure theory, to appear in Combinatorics, Complexity and Chance. A tribute to Dominic Welsh, G. Grimmett and C. McDiarmid, Eds., Oxford University Press, 2006.","DOI":"10.1093\/acprof:oso\/9780198571278.003.0005"},{"key":"684_CR66","unstructured":"Glover, H., Huneke, J.P., Wang, C.S.: 103 graphs that are irreducible for the projective plane, J. Combin. Theory Ser. B 27, 332\u2013370 (1979)"},{"key":"684_CR67","unstructured":"Goddard, W.: Acyclic coloring of planar graphs, Discrete Math. 91, 91\u201394 (1991)"},{"key":"684_CR68","unstructured":"Gutner, S.: The complexity of planar graph choosability, Discrete Math. 159, 119\u2013130 (1996)"},{"key":"684_CR69","unstructured":"Hadwiger, H.: \u00dcber eine Klassifikation der Streckenkomplexe, Vierteljahrsschr. naturforsch. Ges. Z\u00dcrich 88, 133\u2013142 (1943)"},{"key":"684_CR70","doi-asserted-by":"crossref","unstructured":"Halin, R.: S-function for graphs, J. Geometry 8, 171\u2013186 (1976)","DOI":"10.1007\/BF01917434"},{"key":"684_CR71","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n1-\u03b5, Acta Math. 182, 105\u2013142 (1999)"},{"key":"684_CR72","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., Rao, S., Gabow, H.N.: Computing vertex connectivity: New bounds from old techniques, J. Algorithms 34, 222\u2013250 (2000)","DOI":"10.1006\/jagm.1999.1055"},{"key":"684_CR73","doi-asserted-by":"crossref","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems, Wiley-Interscience, 1995.","DOI":"10.1002\/9781118032497"},{"key":"684_CR74","unstructured":"Johnson, T., Thomas, R.: Generating internally four-connected graphs, J. Combin. Theory Ser. B 85, 21\u201358 (2002)"},{"key":"684_CR75","doi-asserted-by":"crossref","unstructured":"Johnson, T., Robertson, N., Seymour, P., Thomas, R.: Diretcted tree-width, J. Combin. Theory Ser. B 82 , 138\u2013154 (2001)","DOI":"10.1006\/jctb.2000.2031"},{"key":"684_CR76","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, L.K.: Contractions to K8, J. Graph Theory 18, 431\u2013448 (1994)","DOI":"10.1002\/jgt.3190180502"},{"key":"684_CR77","unstructured":"Jung, H.A.: Eine Verallgemeinerung des n-fachen Zusammenhangs f\u00fcr Graphen, Math. Ann. 187, 95\u2013103 (1970)"},{"key":"684_CR78","unstructured":"Juvan, M., Marin\u010dek, J., Mohar, B.: Elimination of local bridges, Math. Slovaca 47, 85\u201392 (1997)"},{"key":"684_CR79","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems, Networks 5, 45\u201348 (1975)"},{"key":"684_CR80","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.: k-linked graphs with large girth, J. Graph Theory 45, 48\u201350 (2004)","DOI":"10.1002\/jgt.10150"},{"key":"684_CR81","unstructured":"Kawarabayashi, K.: Excluding a graph with K6--minor, submitted."},{"key":"684_CR82","unstructured":"Kawarabayashi, K.: On the connectivity of minimal counterexamples to Hadwiger's conjecture, to appear in J. Combin. Theory Ser. B."},{"key":"684_CR83","unstructured":"Kawarabayashi, K.: Unavoidable minors in large 5-connected graphs, in preparation."},{"key":"684_CR84","unstructured":"Kawarabayashi, K.: Minors in 7-chromatic graphs, submitted."},{"key":"684_CR85","unstructured":"Kawarabayashi, K., Kostochka, A., Yu, G.: On sufficient degree conditions for a graph to be k-linked, Combin. Probab. Comput. 15, 685\u2013694 (2006)"},{"key":"684_CR86","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Luo, R., Niu, J., Zhang, C.Q.: On structure of k-connected graphs without Kk-minors, Europ. J. Combinatorics 26, 293\u2013308 (2005)","DOI":"10.1016\/j.ejc.2004.01.011"},{"key":"684_CR87","unstructured":"Kawarabayashi, K., Mohar, B.: K4,k-minors in large 9-connected graphs, in preparation."},{"key":"684_CR88","unstructured":"Kawarabayashi, K., Mohar, B.: Approximating chromatic number and list-chromatic number of minor-closed and odd minor-closed classes of graphs, 38th ACM Symposium on Theory of Computing (STOC'06)."},{"key":"684_CR89","unstructured":"Kawarabayashi, K., Mohar, B.: Algorithmic aspects of Hadwiger's Conjecture, submitted, 2005."},{"key":"684_CR90","unstructured":"Kawarabayashi, K., Mohar, B.: A relaxed Hadwiger's Conjecture for list colorings, to appear in J. Combin. Theory Ser. B."},{"key":"684_CR91","unstructured":"Kawarabayashi, K., Mohar, B.: Improved connectivity bound on Kk-minors in large graphs, preprint."},{"key":"684_CR92","unstructured":"Kawarabayashi, K., Mohar, B.: The Erd\u0151s-P\u00f3sa property for K5-minors and half-integral packing, in preparation."},{"key":"684_CR93","unstructured":"Kawarabayashi, K., Toft, B.: Any 7-chromatic graph has K7 or K4,4 as a minor, Combinatorica 25, 327\u2013353 (2005)"},{"key":"684_CR94","unstructured":"Klein, P.N.: A linear-time approximation scheme for TSP for planar weighted graphs, in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pp. 146\u2013155, 2005."},{"key":"684_CR95","doi-asserted-by":"crossref","unstructured":"Koml\u00f3s, J., Szemer\u00e9di, E.: Topological cliques in graphs. II, Combin. Probab. Comput. 5, 79\u201390 (1996)","DOI":"10.1017\/S096354830000184X"},{"key":"684_CR96","unstructured":"Kostochka, A.: Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4, 307\u2013316 (1984)"},{"key":"684_CR97","unstructured":"Kostochka, A.: The minimum Hadwiger number for graphs with a given mean degree of vertices (in Russian), Metody Diskret. Analiz. 38 , 37\u201358 (1982)"},{"key":"684_CR98","unstructured":"Kostochka, A., Prince, N.: On Ks,t-minors in graphs with given average degree, preprint."},{"key":"684_CR99","doi-asserted-by":"crossref","unstructured":"K\u00fchn, D., Osthus, D.: Forcing unbalanced complete bipartite minors, Europ. J. Combinatorics. 26, 75\u201381 (2005)","DOI":"10.1016\/j.ejc.2004.02.002"},{"key":"684_CR100","doi-asserted-by":"crossref","unstructured":"K\u00fchn, D., Osthus, D.: Minors in graphs of large girth, Random Structures Algorithms 22, 213\u2013225 (2003)","DOI":"10.1002\/rsa.10076"},{"key":"684_CR101","unstructured":"K\u00fchn, D., Osthus, D.: Topological minors in graphs of large girth, J. Combin. Theory Ser. B 86, 364\u2013380 (2002)"},{"key":"684_CR102","unstructured":"K\u00fchn, D., Osthus, D.: Complete minors in Ks,s-free graphs, Combinatorica 25, 49\u201364 (2005)"},{"key":"684_CR103","unstructured":"Larman, D.G., Mani, P.: On the existence of certain configurations within graphs and the 1-skeletons of polytopes, Proc. London Math. Soc. 20, 144\u2013160 (1974)"},{"key":"684_CR104","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem, SIAM J. Comput. 9, 615\u2013627 (1980)"},{"key":"684_CR105","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Schrijver, A.: On the null space of a Colin de Verdi\u00e8re matrix, Ann. Inst. Fourier (Grenoble) 49, 1017\u20131026 (1999)","DOI":"10.5802\/aif.1703"},{"key":"684_CR106","unstructured":"Lov\u00e1sz, L., Schrijver, A.: A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126, 1275\u20131285 (1998)"},{"key":"684_CR107","unstructured":"Mader, W.: Homomorphies\u00e4tze f\u00fcr Graphen, Math. Ann. 178, 154\u2013168 (1968)"},{"key":"684_CR108","doi-asserted-by":"crossref","unstructured":"Mader, W.: Existenz n-fach zusammenh\u00e4ngender Teilgraphen in Graphen gen\u00fcgend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37, 86\u201397 (1972)","DOI":"10.1007\/BF02993903"},{"key":"684_CR109","unstructured":"Mader, W.: Topological subgraphs in graphs of large girth, Combinatorica 18, 405\u2013412 (1998)"},{"key":"684_CR110","unstructured":"Mader, W.: private communication."},{"key":"684_CR111","unstructured":"Mahadev, N.V.R., Roberts, F.S., Santhanakrinshnan, P.: 3-choosable complete bipratite graphs, preprint."},{"key":"684_CR112","unstructured":"Maharry, J.: A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80, 179\u2013201 (2000)"},{"key":"684_CR113","doi-asserted-by":"crossref","unstructured":"Maharry, J.: An excluded minor theorem for the octahedron, J. Graph Theory 31, 95\u2013100 (1999)","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<95::AID-JGT2>3.0.CO;2-N"},{"key":"684_CR114","unstructured":"Maharry, J.: An excluded minor theorem for the octahedron plus an edge, preprint."},{"key":"684_CR115","unstructured":"Maharry, J.: Three excluded minor structure theorems, preprint, 2006."},{"key":"684_CR116","unstructured":"Mohar, B.: Combinatorial local planarity and the width of graph embeddings, Canad. J. Math. 44, 1272\u20131288 (1992)"},{"key":"684_CR117","unstructured":"Mohar, B.: Uniqueness and minimality of large face-width embeddings of graphs, Combinatorica 15, 541\u2013556 (1995)"},{"key":"684_CR118","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface, Siam. J. Discrete math. 12, 6\u201326 (1999)"},{"key":"684_CR119","doi-asserted-by":"crossref","unstructured":"Mohar, B.: Graph minors and graphs on surfaces. in ``Surveys in Combinatorics, 2001 (Sussex)'', London Math. Soc. Lecture Note Ser. 288, Cambridge Univ. Press, Cambridge, 2001, pp. 145\u2013163.","DOI":"10.1017\/CBO9780511721328.008"},{"key":"684_CR120","unstructured":"Mohar, B.: Problem of the month, Fall 2003, http:\/\/www.fmf.uni-lj.si\/~mohar\/."},{"key":"684_CR121","unstructured":"Mohar, B., Seymour, P.D.: Coloring locally bipartite graphs on surfaces, J. Combin. Theory, Ser. B 84, 301\u2013310 (2002)"},{"key":"684_CR122","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces, Johns Hopkins University Press, Baltimore, MD, 2001."},{"key":"684_CR123","unstructured":"Myers, J.: The extremal function for unbalanced bipartite minors, Discrete Math. 271, 209\u2013221 (2003)"},{"key":"684_CR124","unstructured":"Myers, J., Thomason, A.: The extremal function for noncomplete graph minors, to appear in Combinatorica."},{"key":"684_CR125","unstructured":"Oporowski, B., Oxley, J., Thomas, R.: Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B 57, 239\u2013257 (1993)"},{"key":"684_CR126","doi-asserted-by":"crossref","unstructured":"Reed, B.: Tree width and tangles: a new connectivity measure and some applications, in ``Surveys in Combinatorics, 1997 (London)'', London Math. Soc. Lecture Note Ser. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 87\u2013162.","DOI":"10.1017\/CBO9780511662119.006"},{"key":"684_CR127","unstructured":"Reed, B.: Mangoes and blueberries, Combinatorica 19, 267\u2013296 (1999)"},{"key":"684_CR128","unstructured":"Reed, B., Seymour, P.D.: Fractional colouring and Hadwiger's conjecture, J. Combin. Theory Ser. B 74, 147\u2013152 (1998)"},{"key":"684_CR129","unstructured":"Robertson, N.: private communication."},{"key":"684_CR130","unstructured":"Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: The four-color theorem, J. Combin. Theory Ser. B 70, 2\u201344 (1997)"},{"key":"684_CR131","unstructured":"3 Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B 36, 39\u201361 (1983)"},{"key":"684_CR132","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width, J. Algorithm 7, 309\u2013322 (1986)","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"684_CR133","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width, J. Combin. Theory Ser. B 36, 49\u201363 (1984)"},{"key":"684_CR134","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B 48, 227\u2013254 (1990)"},{"key":"684_CR135","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41, 92\u2013114 (1986)"},{"key":"684_CR136","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VI. Disjoint paths across a disc, J. Combin. Theory Ser. B 41, 115\u2013138 (1986)"},{"key":"684_CR137","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45, 212\u2013254 (1988)"},{"key":"684_CR138","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VIII. A kuratowski theorem for general surfaces, J. Combin. Theory Ser. B 45, 212\u2013254 (1988)"},{"key":"684_CR139","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. IX. Disjoint crossed paths, J. Combin. Theory Ser. B 49, 40\u201377 (1990)"},{"key":"684_CR140","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B 52, 153\u2013190 (1991)"},{"key":"684_CR141","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XI. Circuits on a surface, J. Combin. Theory Ser. B 60, 72\u2013106 (1994)"},{"key":"684_CR142","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XII. Distance on a surface, J. Combin. Theory Ser. B 64, 240\u2013272 (1995)"},{"key":"684_CR143","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63, 65\u2013110 (1995)"},{"key":"684_CR144","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIV. Extending an embedding, J. Combin. Theory Ser. B 65, 23\u201350 (1995)"},{"key":"684_CR145","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XV. Giant Steps, J. Combin. Theory Ser. B 68, 112\u2013148 (1996)"},{"key":"684_CR146","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 89, 43\u201376 (2003)"},{"key":"684_CR147","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVII. Taming a vortex, J. Combin. Theory Ser. B 77, 162\u2013210 (1999)"},{"key":"684_CR148","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVIII. Tree-decompositions and well-quasi-ordering, J. Combin. Theory Ser. B 89, 77\u2013108 (2003)"},{"key":"684_CR149","unstructured":"3 Robertson, N., Seymour, P.D.: Graph minors. XIX, Well-quasi-ordering on a surface, J. Combin. Theory Ser. B 90, 325\u2013385 (2004)"},{"key":"684_CR150","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner's conjecture, J. Combin. Theory Ser. B 92, 325\u2013357 (2004)"},{"key":"684_CR151","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXI. Graphs with unique linkages, preprint."},{"key":"684_CR152","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXII. Irrelevant vertices in linkage problems, preprint."},{"key":"684_CR153","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXIII. Nash-Williams' immersion conjecture, preprint."},{"key":"684_CR154","unstructured":"Robertson, N., Seymour, P.D.: An outline of a disjoint paths algorithm, in: ``Paths, Flows, and VLSI-Layout,'' B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver (Eds.), Springer-Verlag, Berlin, 1990, pp. 267\u2013292."},{"key":"684_CR155","unstructured":"Robertson, N., Seymour, P.D.: Excluding a graph with one crossing, Contemp. Math. 147, 669\u2013675 (1993)"},{"key":"684_CR156","unstructured":"Robertson, N., Seymour, P.: private communication, unpublished."},{"key":"684_CR157","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Excluding infinite minors, Discrete Math. 95, 303\u2013319 (1991)"},{"key":"684_CR158","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Excluding subdivision of infinite cliques, Trans. Amer. Math. Soc. 332, 211\u2013233 (1992)"},{"key":"684_CR159","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Hadwiger's conjecture for K6-free graphs, Combinatorica 13, 279\u2013361 (1993)"},{"key":"684_CR160","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph, J. Combin. Theory Ser. B 62, 323\u2013348 (1994)"},{"key":"684_CR161","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Excluding infinite clique minors, Memoirs Amer. Math. Soc. 118, AMS, 1995.","DOI":"10.1090\/memo\/0566"},{"key":"684_CR162","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Kuratowski chains, J. Combin. Theory Ser. B 64, 127\u2013154 (1995)"},{"key":"684_CR163","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Petersen family minors, J. Combin. Theory Ser. B64, 155\u2013184 (1995)","DOI":"10.1006\/jctb.1995.1031"},{"key":"684_CR164","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Sachs' linkless embedding conjecture, J. Combin. Theory Ser. B 64, 185\u2013227 (1995)"},{"key":"684_CR165","unstructured":"Robertson, N., Vitray, R.P.: Representativity of surface embeddings, in: ``Paths, Flows, and VLSI-Layout'' (B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver Eds.), Springer-Verlag, Berlin, 1990, pp. 293\u2013328."},{"key":"684_CR166","doi-asserted-by":"crossref","unstructured":"Roychoudhury, A., Sur-Kolay, S.: 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 1026, Springer, 1995, pp. 37\u201351.","DOI":"10.1007\/3-540-60692-0_39"},{"key":"684_CR167","unstructured":"Seese, D.G., Wessel, W.: Grids and their minors, J. Combin. Theory Ser. B 47, 349\u2013360 (1989)"},{"key":"684_CR168","doi-asserted-by":"crossref","unstructured":"Seymour, P.D.: Disjoint paths in graphs, Discrete Math. 29, 293\u2013309 (1980)","DOI":"10.1016\/0012-365X(80)90158-2"},{"key":"684_CR169","unstructured":"Seymour, P.D.: A bound on the excluded minors for a surface, preprint."},{"key":"684_CR170","doi-asserted-by":"crossref","unstructured":"Seymour, P.D., Thomas, R.: Uniqueness of highly representative surface embeddings, J. Graph Theory 23, 337\u2013349 (1996)","DOI":"10.1002\/(SICI)1097-0118(199612)23:4<337::AID-JGT2>3.0.CO;2-S"},{"key":"684_CR171","unstructured":"Shiloach, Y.: A polynomial solution to the undirected two paths problems, J. Assoc. Comput. Mach. 27, 445\u2013456 (1980)"},{"key":"684_CR172","unstructured":"Song, Z., Thomas, R.: The extremal function for K9-minors, J. Combin. Theory Ser. B 96, 240\u2013252 (2006)"},{"key":"684_CR173","unstructured":"Sulanke, T.: Irreducible triangulations of low genus surfaces, preprint, 2006."},{"key":"684_CR174","unstructured":"Thomas, R.: A counterexample to ``Wagner's conjecture'' for infinite graphs, Math. Proc. Cambridge Philos. Soc. 103, 55\u201357 (1988)"},{"key":"684_CR175","unstructured":"Thomas, R.: Well-quasi-ordering infinite graphs with forbidden finite planar minor, Trans. Amer. Math. Soc. 312, 279\u2013313 (1989)"},{"key":"684_CR176","doi-asserted-by":"crossref","unstructured":"Thomas, R.: Recent excluded minor theorems for graphs, in ``Surveys in Combinatorics, 1999 (Canterbury)'', Cambridge Univ. Press, Cambridge, 1999, pp. 201\u2013222.","DOI":"10.1017\/CBO9780511721335.008"},{"key":"684_CR177","doi-asserted-by":"crossref","unstructured":"Thomas, R., Wollan, P.: An improved linear edge bound for graph linkages, Europ. J. Combinatorics 26, 309\u2013324 (2005)","DOI":"10.1016\/j.ejc.2004.02.013"},{"key":"684_CR178","unstructured":"Thomas, R., Wollan, P.: The extremal function for 3-linked graphs, preprint."},{"key":"684_CR179","unstructured":"Thomason, A.: An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95, 261\u2013265 (1984)"},{"key":"684_CR180","unstructured":"Thomason, A.: The extremal function for complete minors, J. Combin. Theory Ser. B 81, 318\u2013338 (2001)"},{"key":"684_CR181","unstructured":"Thomason, A.: Two minor problems, Combin. Probab. Comput. 13, 413\u2013414 (2004)"},{"key":"684_CR182","doi-asserted-by":"crossref","unstructured":"Thomassen, C.: 2-linked graphs, Europ. J. Combinatorics 1, 371\u2013380 (1980)","DOI":"10.1016\/S0195-6698(80)80039-4"},{"key":"684_CR183","unstructured":"Thomassen, C.: Girth in graphs, J. Combin. Theory, Ser. B 35, 129\u2013141 (1983)"},{"key":"684_CR184","doi-asserted-by":"crossref","unstructured":"Thomassen, C.: On the presence of disjoint subgraphs of a specified type, J. Graph Theory 12, 101\u2013111 (1988)","DOI":"10.1002\/jgt.3190120111"},{"key":"684_CR185","unstructured":"Thomassen, C.: Embedding and minors, Handbook of Combinatorics, Vol. 1, Elsevier, Amsterdam, 1995, pp. 301\u2013349."},{"key":"684_CR186","unstructured":"Thomassen, C.: A simpler proof of the excluded minor theorem for higher surfaces, J. Combin. Theory Ser. B 70, 306\u2013311 (1997)"},{"key":"684_CR187","unstructured":"Thomassen, C.: Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B 70, 67\u2013100 (1997)"},{"key":"684_CR188","unstructured":"Thomassen, C.: Every planar graph is 5-choosable, J. Combin. Theory Ser. B 62, 180\u2013181 (1994)"},{"key":"684_CR189","unstructured":"Toft, B.: A survey of Hadwiger's conjecture, Congr. Numer. 115, 249\u2013283 (1996)"},{"key":"684_CR190","doi-asserted-by":"crossref","unstructured":"Tuza, Z.: Graph colorings with local constraints\u2013-a survey, Discuss. Math. Graph Theory 17, 161\u2013228 (1997)","DOI":"10.7151\/dmgt.1049"},{"key":"684_CR191","unstructured":"Vizing, Z.: Coloring the vertices of a graph in prescribed colors. Metody Diskret. Anal. v Teorii Kodov i Schem 29, 3\u201310 (1976) (in Russian)."},{"key":"684_CR192","unstructured":"Voigt, M.: List colourings of planar graphs, Discrete Math. 120, 215\u2013219 (1993)"},{"key":"684_CR193","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114, 570\u2013590 (1937)"},{"key":"684_CR194","unstructured":"Wagner, K.: Beweis einer Abschw\u00e4chung der Hadwiger-Vermutung, Math. Ann. 153, 139\u2013141 (1964)"},{"key":"684_CR195","unstructured":"Woodall, D.R.: Improper colourings of graphs. in: Graph Colourings (ed. R. Nelson and R. J. Wilson), Pitman Research Notes 218, Longman, 1990, pp. 45\u201363."},{"key":"684_CR196","unstructured":"Zha, X., Zhao, Y.: On nonnull separating circuits in embedded graphs, in: Graph structure theory (Seattle, WA, 1991), Contemp. Math. 147, 349\u2013362 (1993)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-006-0684-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-006-0684-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-006-0684-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T01:13:35Z","timestamp":1736817215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-006-0684-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2]]},"references-count":196,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,2]]}},"alternative-id":["684"],"URL":"https:\/\/doi.org\/10.1007\/s00373-006-0684-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2]]}}}