New tools and results in graph minor structure theory

doi:10.1017/CBO9781316106853.008

7 - New tools and results in graph minor structure theory

Published online by Cambridge University Press: 05 July 2015

Sergey Norin

Edited by

Artur Czumaj ,

Agelos Georgakopoulos ,

Daniel Král ,

Vadim Lozin and

Oleg Pikhurko

Show author details

Artur Czumaj: Affiliation:
University of Warwick
Agelos Georgakopoulos: Affiliation:
University of Warwick
Daniel Král: Affiliation:
University of Warwick
Vadim Lozin: Affiliation:
University of Warwick
Oleg Pikhurko: Affiliation:
University of Warwick

Book contents

Get access

Summary

Abstract

Graph minor theory of Robertson and Seymour is a far reaching generalization of the classical Kuratowski–Wagner theorem, which characterizes planar graphs in terms of forbidden minors. We survey new structural tools and results in the theory, concentrating on the structure of large t-connected graphs, which do not contain the complete graph Kt as a minor.

1 Introduction

Graphs in this paper are finite and simple, unless specified otherwise. A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Numerous theorems in structural graph theory describe classes of graphs which do not contain a fixed graph or a collection of graphs as a minor. A classical example of such a description is the Kuratowski–Wagner theorem [92,93].

Theorem 1.1A graph is planar if and only if it does not contain K5 or K3,3 as a minor.

(We will say that G contains H as a minor, if H is isomorphic to a minor of G, and we will use the notation H ≤ G to denote this. The notation is justified as the minor containment is, indeed, a partial order. We say that G is H-minor free if G does not contain H as a minor.)

Clearly a graph is a forest if and only if it does not contain K3 as a minor. In [16] Dirac proved that a graph does not contain K4 as a minor if and only if it is series-parallel. In [93] Wagner characterizes graphs which do not contain K5 as a minor, as follows.

Theorem 1.2A graph does not contain K5 as a minor if and only if it can be obtained by 0-, 1 and 2 and 3-clique sum operations from planar graphs and V8. (The graph V8 is shown on Figure 1.)

Type: Chapter
Information: Surveys in Combinatorics 2015 , pp. 221 - 260

DOI: https://doi.org/10.1017/CBO9781316106853.008 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] N., Alon, P., Seymour, and R., Thomas, A separator theorem for nonplanar graphs, J. Amer. Math. Soc. 3 (1990), no. 4, 801–808.Google Scholar

[2] K., Appel and W., Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490.

[3] K., Appel, W., Haken, and J., Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567.

[4] M., Baker and S., Norine, Riemann–Roch and Abel–Jacobi theory on a finite graph, Advances in Mathematics 215 (2007), no. 2, 766–788.Google Scholar

[5] H. L., Bodlaender, J. R., Gilbert, H., Hafsteinsson, and T., Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms 18 (1995), no. 2, 238–255.Google Scholar

[6] D., Bokal, B., Oporowski, B., Richter, and G., Salazar, Characterizing 2-crossing-critical graphs, 2013. arXiv:1312.3712.

[7] C., Chekuri and J., Chuzhoy, Polynomial bounds for the grid-minor theorem, 2013. arXiv:1305.6577.

[8] M., Chudnovsky, B., Reed, and P., Seymour, The edge-density for K2,t minors, J. Combin. Theory Ser. B 101 (2011), no. 1, 18–46.Google Scholar

[9] K., Corradi and A., Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963), 423–439. MR0200185 (34 #84)Google Scholar

[10] M., DeVos, G., Ding, B., Oporowski, D. P., Sanders, B., Reed, P., Seymour, and D., Vertigan, Excluding any graph as a minor allows a low tree-width 2-coloring, J. Combin. Theory Ser. B 91 (2004), no. 1, 25–41.Google Scholar

[11] R., Diestel, Graph theory, Fourth Edition, Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010.

[12] R., Diestel, T. R., Jensen, K. Yu., Gorbunov, and C., Thomassen, Highly connected sets and the excluded grid theorem, J. Combin. Theory Ser. B 75 (1999), no. 1, 61–73.

[13] R., Diestel, K., Kawarabayashi, T., Müller, and P., Wollan, On the excluded minor structure theorem for graphs of large tree-width, J. Combin. Theory Ser. B 102 (2012), no. 6, 1189–1210.

[14] R., Diestel, K., Kawarabayashi, and P., Wollan, The Erdős-Pósa property for clique minors in highly connected graphs, J. Combin. Theory Ser. B 102 (2012), no. 2, 454–469.

[15] G., Ding, B., Oporowski, R., Thomas, and D., Vertigan, Large nonplanar graphs and an application to crossing-critical graphs, J. Combin. Theory Ser. B 101 (2011), no. 2, 111–121.

[16] G. A., Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 85–92.

[17] G. A., Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964), 69–80.

[18] V., Dujmović, P., Morin, and D. R., Wood, Layered separators in minorclosed families with applications, 2013. arXiv:1306.1595.

[19] Z., Dvořák, A stronger structure theorem for excluded topological minors, 2012. arXiv:1209.0129.

[20] Z., Dvořák, Sublinear separators, fragility and subexponential expansion, 2014. arXiv:1404.7219.

[21] Z., Dvořák and R., Thomas, List-coloring apex-minor-free graphs, 2014. arXiv:1401.1399.

[22] Z., Dvořák and S., Norine, Small graph classes and bounded expansion, J. Combin. Theory Ser. B 100 (2010), no. 2, 171–175.

[23] Z., Dvořák and S., Norin, Treewidth of graphs with balanced separators. manuscript.

[24] D., Eppstein, Diameter and treewidth in minor-closed graph families, Algorithmica 27 (2000), no. 3-4, 275–291. Treewidth.Google Scholar

[25] D., Eppstein, Densities of minor-closed graph families, Electron. J. Combin. 17 (2010), no. 1, Research Paper 136, 21.

[26] J., Fox, Constructing dense graphs with sublinear Hadwiger number. J. Combin. Theory Ser. B, to appear.

[27] J., Geelen, B., Gerards, and G., Whittle, The highly connected matroids in minor-closed classes, 2013. arXiv:1312.5012.

[28] M., Grohe and D., Marx, Structure theorem and isomorphism test for graphs with excluded topological subgraphs, Proceedings of the fortyfourth annual acm symposium on theory of computing, 2012, pp. 173–192.Google Scholar

[29] H., Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133–142.

[30] R., Halin, S-functions for graphs, J. Geometry 8 (1976), no. 1-2, 171–186.

[31] D., Harvey and D., Wood, Parameters tied to treewidth, 2013. arXiv:1312.3401.

[32] D. J., Harvey and D. R., Wood, Cycles of given size in a dense graph, 2015. arXiv:1502.03549.

[33] G., Joret, P., Micek, K. G, Milans, W. T, Trotter, B., Walczak, and R., Wang, Tree-width and dimension, 2013. arXiv:1301.5271.

[34] L. K., Jorgensen, Contractions to K8, J. Graph Theory 18 (1994), no. 5, 431–448.

[35] R., Kapadia and S., Norin, Densities of minor-closed graph classes are rational. in preparation.

[36] K., Kawarabayashi and Y., Kobayashi, Linear min-max relation between the treewidth of h-minor-free graphs and its largest grid, Lipicsleibniz international proceedings in informatics, 2012.

[37] K., Kawarabayashi and B., Mohar, Some recent progress and applications in graph minor theory, Graphs Combin. 23 (2007), no. 1, 1–46.

[38] K., Kawarabayashi, S., Norine, R., Thomas, and P., Wollan, K6 minors in 6-connected graphs of bounded tree-width. submitted.

[39] K., Kawarabayashi, S., Norine, R., Thomas, and P., Wollan, K6 minors in large 6-connected graphs. submitted.

[40] A. V., Kostochka, The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz. 38 (1982), 37–58.

[41] A. V., Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4 (1984), no. 4, 307–316.

[42] A. V., Kostochka and N., Prince, Dense graphs have K3,t minors, Discrete Math. 310 (2010), no. 20, 2637–2654.

[43] A., Leaf and P., Seymour, Treewidth and planar minors (2012). manuscript.

[44] R. J., Lipton and R. E., Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), no. 2, 177–189.

[45] C.-H., Liu and R., Thomas, Well-quasi-ordering graphs by the topological minor relation: Robertson's conjecture. in preparation.

[46] L., Lovász, Graph minor theory, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 1, 75–86 (electronic).

[47] W., Mader, Homomorphiesätze für Graphen, Math. Ann. 178 (1968), 154–168.

[48] J., Maharry, An excluded minor theorem for the octahedron, J. Graph Theory 31 (1999), no. 2, 95–100.

[49] J., Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2000), no. 2, 179–201.

[50] C., McDiarmid, A., Steger, and D. J. A., Welsh, Random graphs from planar and other addable classes, Topics in discrete mathematics, 2006, pp. 231–246.Google Scholar

[51] J., Nešetřil and P., Ossona de Mendez, Grad and classes with bounded expansion. I. Decompositions, European J. Combin. 29 (2008), no. 3, 760–776.

[52] J., Nešetřil, P., Ossona de Mendez, and D. R., Wood, Characterisations and examples of graph classes with bounded expansion, European J. Combin. 33 (2012), no. 3, 350–373.

[53] S., Norin and R., Thomas, Cultivating a vortex. in preparation.

[54] S., Norin and R., Thomas, Linear decompositions of large graphs. in preparation.

[55] S., Norin and R., Thomas, Minors and linkages in large graphs. in preparation.

[56] S., Norin and R., Thomas, Non-planar extensions of subdivisions of planar graphs, 2014. arXiv:1402.1999.

[57] S., Norine, P., Seymour, R., Thomas, and P., Wollan, Proper minorclosed families are small, J. Combin. Theory Ser. B 96 (2006), no. 5, 754–757.

[58] B., Oporowski, J., Oxley, and R., Thomas, Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B 57 (1993), no. 2, 239–257.

[59] B., Reed and D. R., Wood, Forcing a sparse minor, 2014. arXiv:1402.0272.

[60] N., Robertson, D., Sanders, P., Seymour, and R., Thomas, The fourcolour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44.

[61] N., Robertson and P., Seymour, Graph minors. XVIII. Treedecompositions and well-quasi-ordering, J. Combin. Theory Ser. B 89 (2003), no. 1, 77–108.

[62] N., Robertson and P., Seymour, Graph minors. XXI. Graphs with unique linkages, J. Combin. Theory Ser. B 99 (2009), no. 3, 583–616.

[63] N., Robertson and P., Seymour, Graph minors XXIII. Nash-Williams' immersion conjecture, J. Combin. Theory Ser. B 100 (2010), no. 2, 181–205.

[64] N., Robertson and P., Seymour, Graph minors. XXII. Irrelevant vertices in linkage problems, J. Combin. Theory Ser. B 102 (2012), no. 2, 530–563.

[65] N., Robertson, P., Seymour, and R., Thomas, Quickly excluding a planar graph, J. Combin. Theory Ser. B 62 (1994), no. 2, 323–348.

[66] N., Robertson and P. D., Seymour, Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B 35 (1983), no. 1, 39–61.

[67] N., Robertson and P. D., Seymour, Graph minors. III. Planar treewidth, J. Combin. Theory Ser. B 36 (1984), no. 1, 49–64.

[68] N., Robertson and P. D., Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986), no. 3, 309–322.

[69] N., Robertson and P. D., Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986), no. 1, 92–114.

[70] N., Robertson and P. D., Seymour, Graph minors. VI. Disjoint paths across a disc, J. Combin. Theory Ser. B 41 (1986), no. 1, 115–138.

[71] N., Robertson and P. D., Seymour, Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45 (1988), no. 2, 212–254.

[72] N., Robertson and P. D., Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B 48 (1990), no. 2, 227–254.

[73] N., Robertson and P. D., Seymour, Graph minors. IX. Disjoint crossed paths, J. Combin. Theory Ser. B 49 (1990), no. 1, 40–77.

[74] N., Robertson and P. D., Seymour, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B 48 (1990), no. 2, 255–288.

[75] N., Robertson and P. D., Seymour, Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B 52 (1991), no. 2, 153–190.

[76] N., Robertson and P. D., Seymour, Graph minors. XI. Circuits on a surface, J. Combin. Theory Ser. B 60 (1994), no. 1, 72–106.

[77] N., Robertson and P. D., Seymour, Graph minors. XII. Distance on a surface, J. Combin. Theory Ser. B 64 (1995), no. 2, 240–272.

[78] N., Robertson and P. D., Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995), no. 1, 65–110.

[79] N., Robertson and P. D., Seymour, Graph minors. XIV. Extending an embedding, J. Combin. Theory Ser. B 65 (1995), no. 1, 23–50.

[80] N., Robertson and P. D., Seymour, Graph minors. XV. Giant steps, J. Combin. Theory Ser. B 68 (1996), no. 1, 112–148.

[81] N., Robertson and P. D., Seymour, Graph minors. XVII. Taming a vortex, J. Combin. Theory Ser. B 77 (1999), no. 1, 162–210.

[82] N., Robertson and P. D., Seymour, Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 89 (2003), no. 1, 43–76.

[83] N., Robertson and P. D., Seymour, Graph minors. XIX. Well-quasiordering on a surface, J. Combin. Theory Ser. B 90 (2004), no. 2, 325–385.

[84] N., Robertson and P. D., Seymour, Graph minors. XX. Wagner's conjecture, J. Combin. Theory Ser. B 92 (2004), no. 2, 325–357.

[85] N., Robertson, P., Seymour, and R., Thomas, Hadwiger's conjecture for K6-free graphs, Combinatorica 13 (1993), no. 3, 279–361.

[86] P. D., Seymour and R., Thomas, Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B 58 (1993), no. 1, 22–33.

[87] Z.-X., Song and R., Thomas, The extremal function for K9 minors, J. Combin. Theory Ser. B 96 (2006), no. 2, 240–252.

[88] R., Thomas, Recent excluded minor theorems for graphs, Surveys in combinatorics, 1999 (Canterbury), 1999, pp. 201–222.

[89] A., Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95 (1984), no. 2, 261–265.

[90] A., Thomason, The extremal function for complete minors, J. Combin. Theory Ser. B 81 (2001), no. 2, 318–338.

[91] J., van Dobben de Bruyn and D., Gijswijt, A lower bound on the gonality of finite graphs, 2014. arXiv:1407.7055.

[92] K., Wagner, Sur le probléme des courbes gauches en topologie, Fundamenta Mathematicae 15 (1930), 271–283.

[93] K., Wagner, Über eine Eigenschaft der ebenen Komplexe, Mathematische Annalen 114 (1937), 570–590.

[94] K., Wagner, Beweis einer Abschwächung der Hadwiger-Vermutung, Math. Ann. 153 (1964), 139–141.