View source for Homeomorphism (graph theory)

In [[graph theory]], an [[undirected graph]] ''H'' is called a '''minor''' of the graph ''G'' if ''H'' can be formed from ''G'' by deleting edges and vertices and by [[edge contraction|contracting edges]].

The theory of graph minors began with [[Wagner's theorem]] that a graph is [[planar graph|planar]] if and only if its minors do not include the [[complete graph]] ''K''<sub>5</sub> nor the [[complete bipartite graph]] ''K''<sub>3,3</sub>.<ref name="w">{{harvtxt|Lovász|2006}}, p. 77; {{harvtxt|Wagner|1937a}}.</ref> The [[Robertson–Seymour theorem]] implies that an analogous [[forbidden minors|forbidden minor characterization]] exists for every property of graphs that is preserved by deletions and edge contractions.<ref name="rst">{{harvtxt|Lovász|2006}}, theorem 4, p. 78; {{harvtxt|Robertson|Seymour|2004}}.</ref>
For every fixed graph ''H'', it is possible to test whether ''H'' is a minor of an input graph ''G'' in [[polynomial time]];<ref name="rs95"/> together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.<ref name="fl88"/>

Other results and conjectures involving graph minors include the [[graph structure theorem]], according to which the graphs that do not have ''H'' as a minor may be formed by gluing together simpler pieces, and [[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]] relating the inability to [[graph coloring|color a graph]] to the existence of a large [[complete graph]] as a minor of it. Important variants of graph minors include the topological minors and immersion minors.

==Definitions==
An edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices it used to connect. An [[undirected graph]] ''H'' is a minor of another undirected graph ''G'' if a graph isomorphic to ''H'' can be obtained from ''G'' by contracting some edges, deleting some edges, and deleting some isolated vertices.  The order in which a sequence of such contractions and deletions is performed on ''G'' does not affect the resulting graph ''H''.

Graph minors are often studied in the more general context of [[matroid minor]]s. In this context, it is common to assume that all graphs are connected, with [[loop (graph theory)|self-loops]] and [[multiple edge]]s allowed (that is, they are [[multigraph]]s rather than simple graphs); the contraction of a loop and the deletion of a [[cut-edge]] are forbidden operations. This point of view has the advantage that edge deletions leave the [[rank (graph theory)|rank]] of a graph unchanged, and edge contractions always reduce the rank by one.

In other contexts (such as with the study of [[pseudoforest]]s) it makes more sense to allow the deletion of a cut-edge, and to allow disconnected graphs, but to forbid multigraphs. In this variation of graph minor theory, a graph is always simplified after any edge contraction to eliminate its self-loops and multiple edges.<ref>{{harvtxt|Lovász|2006}} is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p. 76 that "parallel edges and loops are allowed" but on p. 77 he states that "a graph is a forest if and only if it does not contain the triangle ''K''<sub>3</sub> as a minor", true only for simple graphs.</ref>

==Example==
In the following example, graph H is a minor of graph G:

H. [[Image:GraphMinorExampleA.png|100px|graph H]]

G. [[Image:GraphMinorExampleB.svg|200px|graph G]]

The following diagram illustrates this. First construct a subgraph of G by deleting the dashed edges (and the resulting isolated vertex), and then contract the gray edge (merging the two vertices it connects):

[[Image:GraphMinorExampleC.svg|190px|transformation from G to H]]

== Major results and conjectures ==
It is straightforward to verify that the graph minor [[binary relation|relation]] forms a [[partial order]] on the isomorphism classes of undirected graphs: it is [[Transitive relation|transitive]] (a minor of a minor of ''G'' is a minor of ''G'' itself), and ''G'' and ''H'' can only be minors of each other if they are isomorphic because any nontrivial minor operation removes edges or vertices. A [[deep result]] by [[Neil Robertson (mathematician)|Neil Robertson]] and [[Paul Seymour (mathematician)|Paul Seymour]] states that this partial order is actually a [[well-quasi-ordering]]:  if an infinite list ''G''<sub>1</sub>, ''G''<sub>2</sub>,... of finite graphs is given, then there always exist two indices ''i'' < ''j'' such that ''G''<sub>''i''</sub> is a minor of ''G''<sub>''j''</sub>. Another equivalent way of stating this is that any set of graphs can have only a finite number of [[minimal element]]s under the minor ordering.<ref>{{harvtxt|Diestel|2005}}, Chapter 12: Minors, Trees, and WQO; {{harvtxt|Robertson|Seymour|2004}}.</ref> This result proved a conjecture formerly known as Wagner's conjecture, after [[Klaus Wagner]]; Wagner had conjectured it long earlier, but only published it in 1970.<ref>{{harvtxt|Lovász|2006}}, p. 76.</ref>

In the course of their proof, Seymour and Robertson also prove the [[graph structure theorem]] in which they determine, for any fixed graph ''H'', the rough structure of any graph which does not have ''H'' as a minor.  The statement of the theorem is itself long and involved, but in short it establishes that such a graph must have the structure of a [[clique-sum]] of smaller graphs that are modified in small ways from graphs [[graph embedding|embedded]] on surfaces of bounded [[Genus (mathematics)|genus]].
Thus, their theory establishes fundamental connections between graph minors and [[graph embedding|topological embeddings]] of graphs.<ref>{{harvtxt|Lovász|2006}}, pp. 80–82; {{harvtxt|Robertson|Seymour|2003}}.</ref>
 
For any graph ''H'', the simple ''H''-minor-free graphs must be [[sparse graph|sparse]], which means that the number of edges is less than some constant multiple of the number of vertices.<ref>{{harvtxt|Mader|1967}}.</ref> More specifically, if ''H'' has ''h'' vertices, then a simple ''n''-vertex simple ''H''-minor-free graph can have at most <math>\scriptstyle O(nh\sqrt{\log h})</math> edges, and some ''K<sub>h</sub>''-minor-free graphs have at least this many edges.<ref>{{harvtxt|Kostochka|1982}}; {{harvtxt|Kostochka|1984}}; {{harvtxt|Thomason|1984}}; {{harvtxt|Thomason|2001}}.</ref> Additionally, the ''H''-minor-free graphs have a separator theorem similar to the [[planar separator theorem]] for planar graphs: for any fixed ''H'', and any ''n''-vertex ''H''-minor-free graph ''G'', it is possible to find a subset of O(√''n'') vertices the removal of which splits ''G'' into two (possibly disconnected) subgraphs with at most 2''n''/3 vertices per subgraph.<ref>{{harvtxt|Alon|Seymour|Thomas|1990}}; {{harvtxt|Plotkin|Rao|Smith|1994}}; {{harvtxt|Reed|Wood|2009}}.</ref>

The [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] in graph theory proposes that if a graph ''G'' does not contain a minor isomorphic to the [[complete graph]] on ''k'' vertices, then ''G'' has a [[graph coloring|proper coloring]] with ''k''&nbsp;&minus;&nbsp;1 colors.<ref>{{harvtxt|Hadwiger|1943}}.</ref> The case ''k''&nbsp;=&nbsp;5 is a restatement of the [[four color theorem]]. The Hadwiger conjecture has been proven for ''k''&nbsp;≤&nbsp;6,<ref>{{harvtxt|Robertson|Seymour|Thomas|1993}}.</ref> but is unknown in the general case. {{harvtxt|Bollobás|Catlin|Erdős|1980}} call it “one of the deepest unsolved problems in graph theory.” Another result relating the four-color theorem to graph minors is the [[snark theorem]] announced by Robertson, Sanders, Seymour, and Thomas, a strengthening of the four-color theorem conjectured by [[W. T. Tutte]] and stating that any [[Bridge (graph theory)|bridgeless]] [[cubic graph|3-regular graph]] that requires four colors in an [[edge coloring]] must have the [[Petersen graph]] as a minor.<ref>{{harvtxt|Thomas|1999}}; {{harvtxt|Pegg|2002}}.</ref>

==Minor-closed graph families== <!-- "Minor-closed graph family" redirects here -->
{{Details|Robertson–Seymour theorem|minor-closed graph families, including a list of some}}

Many families of graphs have the property that every minor of a graph in ''F'' is also in ''F''; such a class is said to be ''minor-closed''. For instance, in any [[planar graph]], or any [[graph embedding|embedding]] of a graph on a fixed [[2-manifold|topological surface]], neither the removal of edges nor the contraction of edges can increase the [[genus (mathematics)|genus]] of the embedding; therefore, planar graphs and the graphs embeddable on any fixed surface form minor-closed families.

If ''F'' is a minor-closed family, then (because of the well-quasi-ordering property of minors) among the graphs that do not belong to ''F'' there is a finite set ''X'' of minor-minimal graphs. These graphs are [[Forbidden graph characterization|forbidden minors]] for ''F'': a graph belongs to ''F'' if and only if it does not contain as a minor any graph in ''X''. That is, every minor-closed family ''F'' can be characterized as the family of ''X''-minor-free graphs for some finite set ''X'' of forbidden minors.<ref name="rst"/>
The best-known example of a characterization of this type is [[Wagner's theorem]] characterizing the planar graphs as the graphs having neither K<sub>5</sub> nor K<sub>3,3</sub> as minors.<ref name="w"/>

In some cases, the properties of the graphs in a minor-closed family may be closely connected to the properties of their excluded minors. For example a minor-closed graph family ''F'' has bounded [[pathwidth]] if and only if its forbidden minors include a [[tree (graph theory)|forest]],<ref>{{harvtxt|Robertson|Seymour|1983}}.</ref> ''F'' has bounded [[tree-depth]] if and only if its forbidden minors include a disjoint union of [[path graph]]s, ''F'' has bounded [[treewidth]] if and only if its forbidden minors include a [[planar graph]],<ref>{{harvtxt|Lovász|2006}}, Theorem 9, p. 81; {{harvtxt|Robertson|Seymour|1986}}.</ref> and ''F'' has bounded local treewidth (a functional relationship between [[diameter (graph theory)|diameter]] and treewidth) if and only if its forbidden minors include an [[apex graph]] (a graph that can be made planar by the removal of a single vertex).<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004}}.</ref> If ''H'' can be drawn in the plane with only a single crossing (that is, it has [[crossing number (graph theory)|crossing number]] one) then the ''H''-minor-free graphs have a simplified structure theorem in which they are formed as clique-sums of planar graphs and graphs of bounded treewidth.<ref>{{harvtxt|Robertson|Seymour|1993}}; {{harvtxt|Demaine|Hajiaghayi|Thilikos|2002}}.</ref> For instance, both ''K''<sub>5</sub> and ''K''<sub>3,3</sub> have crossing number one, and as Wagner showed the  ''K''<sub>5</sub>-free graphs are exactly the 3-clique-sums of planar graphs and the eight-vertex [[Wagner graph]], while the ''K''<sub>3,3</sub>-free graphs are exactly the 2-clique-sums of planar graphs and&nbsp;''K''<sub>5</sub>.<ref>{{harvtxt|Wagner|1937a}}; {{harvtxt|Wagner|1937b}}; {{harvtxt|Hall|1943}}.</ref>

==Variations==
===Topological minors=== <!--Topological minor redirects here-->
A graph ''H'' is called a '''topological minor''' of a graph ''G'' if a [[Subdivision (graph theory)|subdivision]] of ''H'' is [[Graph isomorphism|isomorphic]] to a [[Glossary of graph theory#Subgraphs|subgraph]] of ''G''.<ref>{{Harvnb|Diestel|2005|p=20}}</ref> It is easy to see that every topological minor is also a minor. The converse however is not true in general (for instance the [[complete graph]] ''K''<sub>5</sub> in the [[Petersen graph]] is a minor but not a topological one), but holds for graph with maximum degree not greater than three.<ref>{{Harvnb|Diestel|2005|p=22}}</ref>

The topological minor relation is not a well-quasi-ordering on the set of finite graphs{{sfnp|Ding|1996}} and hence the result of Robertson and Seymour does not apply to topological minors. However it is straightforward to construct finite forbidden topological minor characterizations from finite forbidden minor characterizations by replacing every branch set with ''k'' outgoing edges by every tree on ''k'' leaves that has down degree at least two.

===Immersion minor===
A graph operation called ''lifting'' is central in a concept called ''immersions''.  The ''lifting'' is an operation on adjacent edges.  Given three vertices ''v'', ''u'', and ''w'', where ''(v,u)'' and ''(u,w)'' are edges in the graph, the lifting of ''vuw'', or equivalent of ''(v,u), (u,w)'' is the operation that deletes the two edges ''(v,u)'' and ''(u,w)'' and adds the edge ''(v,w)''.  In the case where ''(v,w)'' already was present, ''v'' and ''w'' will now be connected by more than one edge, and hence this operation is intrinsically a multi-graph operation.

In the case where a graph ''H'' can be obtained from a graph ''G'' by a sequence of lifting operations (on ''G'') and then finding an isomorphic subgraph, we say that ''H'' is an immersion minor of ''G''.

The immersion minor relation is a well-quasi-ordering on the set of finite graphs and hence the result of Robertson and Seymour applies to immersion minors.  This furthermore means that every immersion minor-closed family is characterized by a finite family of forbidden immersion minors.

There is yet another way of defining immersion minors, which is equivalent to the lifting operation.  We say that ''H'' is an immersion minor of ''G'' if there exists an injective mapping from vertices in ''H'' to vertices in ''G'' where the images of adjacent elements of ''H'' are connected in ''G'' by edge-disjoint paths.

===Shallow minors===
A [[shallow minor]] of a graph ''G'' is a minor in which the edges of ''G'' that were contracted to form the minor form a collection of disjoint subgraphs with low [[distance (graph theory)|diameter]]. Shallow minors interpolate between the theories of graph minors and subgraphs, in that shallow minors with high depth coincide with the usual type of graph minor, while the shallow minors with depth zero are exactly the subgraphs.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}.</ref> They also allow the theory of graph minors to be extended to classes of graphs such as the [[1-planar graph]]s that are not closed under taking minors.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, pp. 319–321.</ref>

==Algorithms==
The problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a minor is NP-complete in general; for instance, if ''H'' is a [[cycle graph]] with the same number of vertices as ''G'', then ''H'' is a minor of ''G'' if and only if ''G'' contains a [[Hamiltonian cycle]]. However, when ''G'' is part of the input but ''H'' is fixed, it can be solved in polynomial time. More specifically, the running time for testing whether ''H'' is a minor of ''G'' in this case is O(''n''<sup>3</sup>), where ''n'' is the number of vertices in ''G'' and the [[big O notation]] hides a constant that depends superexponentially on ''H''.<ref name="rs95">{{harvtxt|Robertson|Seymour|1995}}.</ref> Thus, by applying the polynomial time algorithm for testing whether a given graph contains any of the forbidden minors, it is possible to recognize the members of any minor-closed family in [[polynomial time]]. However, in order to apply this result constructively, it is necessary to know what the forbidden minors of the graph family are.<ref name="fl88">{{harvtxt|Fellows|Langston|1988}}.</ref>

==Notes==
{{reflist|2}}

==References==
{{refbegin|2}}
*{{citation
 | last1 = Alon | first1 = Noga | author1-link = Noga Alon
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.2307/1990903
 | mr = 1065053
 | journal = [[Journal of the American Mathematical Society]]
 | pages = 801–808
 | title = A separator theorem for nonplanar graphs
 | issue = 4
 | url = http://www.ams.org/journals/jams/1990-03-04/S0894-0347-1990-1065053-0/home.html
 | volume = 3
 | year = 1990
 | jstor = 1990903}}.
*{{citation
 | last1 = Bollobás | first1 = B. | author1-link = Béla Bollobás
 | last2 = Catlin | first2 = P. A.
 | last3 = Erdős | first3 = Paul | author3-link = Paul Erdős
 | journal = [[European Journal of Combinatorics]]
 | pages = 195–199
 | title = Hadwiger's conjecture is true for almost every graph
 | url = http://www2.renyi.hu/~p_erdos/1980-10.pdf
 | volume = 1
 | year = 1980}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | doi = 10.1007/s00453-004-1106-1
 | issue = 3
 | journal = Algorithmica
 | pages = 211–215
 | title = Diameter and treewidth in minor-closed graph families, revisited
 | url = http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/
 | volume = 40
 | year = 2004}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | last3 = Thilikos | first3 = Dimitrios M.
 | contribution = 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor
 | doi = 10.1007/3-540-45753-4_8
 | pages = 67–80
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002)
 | volume = 2462
 | year = 2002}}
*{{citation
 | last = Diestel | first = Reinhard
 | edition = 3rd
 | isbn = 978-3-540-26183-4
 | location = Berlin, New York
 | publisher = Springer-Verlag
 | title = Graph Theory
 | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 | year = 2005}}.
*{{citation
 | last = Ding | first = Guoli
 | doi = 10.1006/jctb.1996.0002
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1368512
 | pages = 11–23
 | series = Series B
 | title = Excluding a long double path minor
 | volume = 66
 | year = 1996}}.
*{{citation
 | last = Eppstein | first = David | authorlink = David Eppstein
 | doi = 10.1007/s004530010020
 | arxiv=math.CO/9907126
 | mr = 2001c:05132
 | journal = Algorithmica
 | pages = 275–291
 | title = Diameter and treewidth in minor-closed graph families
 | volume = 27
 | year = 2000}}.
*{{citation
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston
 | doi = 10.1145/44483.44491
 | issue = 3
 | journal = [[Journal of the ACM]]
 | pages = 727–739
 | title = Nonconstructive tools for proving polynomial-time decidability
 | volume = 35
 | year = 1988}}.
*{{citation
 | last = Hadwiger | first = Hugo | author-link = Hugo Hadwiger
 | journal = Vierteljschr. Naturforsch. Ges. Zürich
 | pages = 133–143
 | title = Über eine Klassifikation der Streckenkomplexe
 | volume = 88
 | year = 1943}}.
*{{citation
 | last = Hall | first = Dick Wick
 | doi = 10.1090/S0002-9904-1943-08065-2
 | issue = 12
 | journal = [[Bulletin of the American Mathematical Society]]
 | pages = 935–936
 | title = A note on primitive skew curves
 | volume = 49
 | year = 1943}}.
*{{citation
 | last = Kostochka | first = Alexandr V.
 | journal = Metody Diskret. Analiz.
 | language = Russian
 | pages = 37–58
 | title = The minimum Hadwiger number for graphs with a given mean degree of vertices
 | volume = 38
 | year = 1982}}.
*{{citation
 | last = Kostochka | first = Alexandr V.
 | doi = 10.1007/BF02579141
 | journal = Combinatorica
 | pages = 307–316
 | title = Lower bound of the Hadwiger number of graphs by their average degree
 | volume = 4
 | year = 1984}}.
*{{citation
 | last = Lovász | first = László | author-link = László Lovász
 | doi = 10.1090/S0273-0979-05-01088-8
 | issue = 1
 | journal = [[Bulletin of the American Mathematical Society]]
 | pages = 75–86
 | title = Graph minor theory
 | volume = 43
 | year = 2006}}.
*{{citation
 | last = Mader | first = Wolfgang
 | doi = 10.1007/BF01364272
 | issue = 4
 | journal = Mathematische Annalen
 | pages = 265–268
 | title = Homomorphieeigenschaften und mittlere Kantendichte von Graphen
 | volume = 174
 | year = 1967}}.
*{{citation
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | mr = 2920058
 | pages = 62–65
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012}}.
*{{citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf | doi = 10.1109/TED.2002.1003756}}.
*{{citation
 | last1 = Plotkin | first1 = Serge
 | last2 = Rao | first2 = Satish
 | last3 = Smith | first3 = Warren D.
 | contribution = Shallow excluded minors and improved graph decompositions
 | pages = 462–470
 | title = Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994)
 | url = http://www.stanford.edu/~plotkin/lminors.ps
 | year = 1994}}.
*{{citation
 | last1 = Reed | first1 = Bruce | authorlink = Bruce Reed (mathematician)
 | last2 = Wood | first2 = David R.
 | doi = 10.1145/1597036.1597043
 | issue = 4
 | journal = ACM Transactions on Algorithms
 | pages = Article 39
 | title = A linear-time algorithm to find a separator in a graph excluding a minor
 | volume = 5
 | year = 2009}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/0095-8956(83)90079-5
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 39–61
 | title = Graph minors. I. Excluding a forest
 | volume = 35
 | year = 1983}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/0095-8956(86)90030-4
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 92–114
 | title = Graph minors. V. Excluding a planar graph
 | volume = 41
 | year = 1986}}
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | contribution = Excluding a graph with one crossing
 | editor1-last = Robertson | editor1-first = Neil
 | editor2-last = Seymour | editor2-first = Paul
 | pages = 669–675
 | publisher = [[American Mathematical Society]]
 | series = Contemporary Mathematics
 | title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
 | volume = 147
 | year = 1993}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1006/jctb.1995.1006
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 65–110
 | title = Graph Minors. XIII. The disjoint paths problem
 | volume = 63
 | year = 1995}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/S0095-8956(03)00042-X
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 43–76
 | title = Graph Minors. XVI. Excluding a non-planar graph
 | volume = 89
 | year = 2003}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/j.jctb.2004.08.001
 | issue = 2
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 325–357
 | title = Graph Minors. XX. Wagner's conjecture
 | volume = 92
 | year = 2004}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.1007/BF01202354
 | journal = [[Combinatorica]]
 | pages = 279–361
 | title = Hadwiger's conjecture for ''K''<sub>6</sub>-free graphs
 | url = http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf
 | volume = 13
 | year = 1993}}.
*{{citation
 | last = Thomas | first = Robin | authorlink = Robin Thomas (mathematician)
 | contribution = Recent excluded minor theorems for graphs
 | location = Cambridge
 | mr = 1725004
 | pages = 201–222
 | publisher = Cambridge Univ. Press
 | series = London Math. Soc. Lecture Note Ser.
 | title = Surveys in combinatorics, 1999 (Canterbury)
 | url=http://people.math.gatech.edu/~thomas/PAP/bcc.pdf
 | volume = 267
 | year = 1999}}.
*{{citation
 | last = Thomason | first = Andrew
 | doi = 10.1017/S0305004100061521
 | issue = 2
 | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]
 | pages = 261–265
 | title = An extremal function for contractions of graphs
 | volume = 95
 | year = 1984}}.
*{{citation
 | last = Thomason | first = Andrew
 | doi = 10.1006/jctb.2000.2013
 | issue = 2
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 318–338
 | title = The extremal function for complete minors
 | volume = 81
 | year = 2001}}.
*{{citation
 | last = Wagner | first = Klaus | author-link = Klaus Wagner
 | doi = 10.1007/BF01594196
 | journal = Math. Ann.
 | pages = 570–590
 | title = Über eine Eigenschaft der ebenen Komplexe
 | volume = 114
 | year = 1937a}}.
*{{citation
 | last = Wagner | first = Klaus | author-link = Klaus Wagner
 | journal = Deutsche Mathematik
 | pages = 280–285
 | title = Über eine Erweiterung des Satzes von Kuratowski
 | volume = 2
 | year = 1937b}}.
{{refend}}

==External links==
*{{mathworld|urlname=GraphMinor|title=Graph Minor}}

{{DEFAULTSORT:Minor (Graph Theory)}}
[[Category:Graph minor theory| ]]
[[Category:Graph theory objects]]