Editing Graph minor (section)

==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#subgraph|subgraph]] of ''G''.<ref>{{Harvnb|Diestel|2005|p=20}}</ref> 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.

===Induced minors===
A graph ''H'' is called an '''induced minor''' of a graph ''G'' if it can be obtained from an induced subgraph of ''G'' by contracting edges. Otherwise, ''G'' is said to be ''H''-induced minor-free.<ref>{{harvtxt|Błasiok|Kamiński|Raymond|Trunck|2015}}</ref>

===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''.
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.

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.

In [[graph drawing]], immersion minors arise as the [[planarization]]s of [[planar graph|non-planar graphs]]: from a drawing of a graph in the plane, with crossings, one can form an immersion minor by replacing each crossing point by a new vertex, and in the process also subdividing each crossed edge into a path. This allows drawing methods for planar graphs to be extended to non-planar graphs.{{sfnp|Buchheim|Chimani|Gutwenger|Jünger|2014}}

===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 [[Diameter (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>

===Parity conditions===
An alternative and equivalent definition of a graph minor is that ''H'' is a minor of ''G'' whenever the vertices of ''H'' can be represented by a collection of vertex-disjoint subtrees of ''G'', such that if two vertices are adjacent in ''H'', there exists an edge with its endpoints in the corresponding two trees in ''G''.
An [[odd minor]] restricts this definition by adding parity conditions to these subtrees. If ''H'' is represented by a collection of subtrees of ''G'' as above, then ''H'' is an odd minor of ''G'' whenever it is possible to assign two colors to the vertices of ''G'' in such a way that each edge of ''G'' within a subtree is properly colored (its endpoints have different colors) and each edge of ''G'' that represents an adjacency between two subtrees is monochromatic (both its endpoints are the same color). Unlike for the usual kind of graph minors, graphs with forbidden odd minors are not necessarily sparse.<ref>{{citation
 | last1 = Kawarabayashi | first1 = Ken-ichi | author1-link = Ken-ichi Kawarabayashi
 | last2 = Reed | first2 = Bruce | author2-link = Bruce Reed (mathematician)
 | last3 = Wollan | first3 = Paul
 | contribution = The graph minor algorithm with parity conditions
 | doi = 10.1109/focs.2011.52
 | pages = 27–36
 | publisher = Institute of Electrical and Electronics Engineers
 | title = 52nd Annual IEEE Symposium on Foundations of Computer Science
 | year = 2011| s2cid = 17385711 }}.</ref> The [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]], that ''k''-chromatic graphs necessarily contain ''k''-vertex [[complete graph]]s as minors, has also been studied from the point of view of odd minors.<ref>{{citation
 | last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
 | last2 = Gerards | first2 = Bert
 | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician)
 | last4 = Seymour | first4 = Paul | author4-link = Paul Seymour (mathematician)
 | last5 = Vetta | first5 = Adrian
 | doi = 10.1016/j.jctb.2008.03.006
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 2467815
 | pages = 20–29
 | series = Series B
 | title = On the odd-minor variant of Hadwiger's conjecture
 | volume = 99
 | year = 2009| url = https://ir.cwi.nl/pub/13651 | doi-access = free
 }}.</ref>

A different parity-based extension of the notion of graph minors is the concept of a [[bipartite minor]], which produces a [[bipartite graph]] whenever the starting graph is bipartite. A graph ''H'' is a bipartite minor of another graph ''G'' whenever ''H'' can be obtained from ''G'' by deleting vertices, deleting edges, and collapsing pairs of vertices that are at distance two from each other along a [[peripheral cycle]] of the graph. A form of [[Wagner's theorem]] applies for bipartite minors: A bipartite graph ''G'' is a [[planar graph]] if and only if it does not have the [[utility graph]] ''K''<sub>3,3</sub> as a bipartite minor.<ref>{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Kalai | first2 = Gil | author2-link = Gil Kalai
 | last3 = Nevo | first3 = Eran
 | last4 = Novik | first4 = Isabella | author4-link = Isabella Novik
 | last5 = Seymour | first5 = Paul | author5-link = Paul Seymour (mathematician)
 | arxiv = 1312.0210
 | doi = 10.1016/j.jctb.2015.08.001
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 3425242
 | pages = 219–228
 | series = Series B
 | title = Bipartite minors
 | volume = 116
 | year = 2016| s2cid = 14571660 }}.</ref>