Minor (graph theory)

In graph theory , minors are certain graphs that can be obtained from another graph by edge contraction and by leaving out edges or nodes . In addition to the subgraph relation and the subdivision relation, the minor relation is one of the most important relations in graph theory and allows many in-depth theorems such as B. Kuratowski's theorem or Robertson and Seymour's minor theorem .

definition

All graphs mentioned are always assumed to be simple .

Minor

Replacing the nodes of a graph by disjoint connected graphs and edges by - -edges, we obtain a new graph, which is referred to ( for inflated). This name derives from the fact that replacing the nodes with graphs increases the size of the original graph. If a graph now contains a , it is called a minor of . ${\displaystyle x\in V}$ ${\displaystyle G}$ ${\displaystyle G_{x}}$ ${\displaystyle xy}$ ${\displaystyle G_{x}}$ ${\displaystyle G_{y}}$ ${\displaystyle IG}$ ${\displaystyle I}$ ${\displaystyle Z}$ ${\displaystyle IG}$ ${\displaystyle G}$ ${\displaystyle Z}$

Topological minor

Is a graph , so is a graph partitioning graph of if it by subdividing edges of emerged. The nodes of , which are also contained in, are then called branching nodes, all other nodes are called subdivision nodes . Branch nodes inherit their degree of , subdivision nodes are all of degree two. If a graph contains a subdivision graph of a graph , it is called a topological minor of . ${\displaystyle G}$ ${\displaystyle TG}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle TG}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle TG}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle Z}$

Equivalent Definitions

The following definitions are also occasionally found in the literature:

Minor

A graph is called a minor of if it contains a subgraph that results from edge contraction . ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle Z}$ ${\displaystyle G}$

Topological minor

A graph is called a topological minor of if it contains a subdivision graph of . ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle Z}$ ${\displaystyle G}$

example

Minor

On the far left is the complete graph with three nodes . This arises from edge contraction from the graph , which in turn is contained in. is therefore a minor of . ${\displaystyle K_{3}}$ ${\displaystyle IK_{3}}$ ${\displaystyle Y}$ ${\displaystyle K_{3}}$ ${\displaystyle Y}$

Topological minor

On the far left is the complete graph with three nodes and a subdivision graph in the middle . The subdivision graph is contained in the graph , so it is a topological minor of . ${\displaystyle Z}$ ${\displaystyle K_{3}}$ ${\displaystyle Z}$

properties

A , interpreted as . The nodes of the subdivision graph are assigned to the various graphs which the nodes replace. Not every node of the has to be replaced by a new graph. ${\displaystyle TK_{3}}$ ${\displaystyle IK_{3}}$ ${\displaystyle K_{3}}$

• The minor relation defines an order relation on the finite graph , that is, it is reflexive , transitive and antisymmetric . ${\displaystyle G\preccurlyeq H:\Longleftrightarrow G{\text{ ist Minor von }}H}$
• Every subgraph of a graph is also a minor of this graph.
• Each is also a . So every topological minor is also an ordinary minor. ${\displaystyle TX}$ ${\displaystyle IX}$
• Not every minor is also a topological minor. An example of this is the Petersen graph and its minor . ${\displaystyle K_{5}}$
• The minor relation defines a quasi-order on the finite graph. This theorem is also known as the minor theorem.
• The determinant of the adjacency matrix of a minor is precisely the minor corresponding to the subgraph in the sense of the matrix calculation of the adjacency matrix of the original graph .

variants

Topological Minors

A graph is a topological minor of a graph referred to when a partition graph from isomorphic to a subgraph of is. It is easy to see that every topological minor is also a minor. The converse is generally not true, but is true for graphs with a maximum nodal degree of three or less . The complete graph in the Petersen graph is a minor, but not a topological minor. The topological minor relation is not a well-quasi-order on the set of finite graphs , and therefore Robertson and Seymour's minor theorem does not hold for topological minors. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle K_{5}}$

Induced Minors

A graph is referred to as the induced minor of a graph if it can be obtained from an induced subgraph of by contracting edges . Otherwise it is called -induced and free of minors. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$

Immersion minors

A graph operation called lifting is central to a concept called immersion . Lifting takes place on adjacent edges . With three nodes , and , where and are edges in the graph , lifting vuw, or the equivalent of , is the operation that removes the two edges and and adds the edge . In the case where it already existed, the nodes and are now connected by more than one edge, and so this operation is in itself a multigraph operation. ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle (v,u)}$ ${\displaystyle (u,w)}$ ${\displaystyle (v,u)}$ ${\displaystyle (u,w)}$ ${\displaystyle (v,u)}$ ${\displaystyle (u,w)}$ ${\displaystyle (v,w)}$ ${\displaystyle (v,w)}$ ${\displaystyle v}$ ${\displaystyle w}$

In the case where a graph can be obtained from a graph by a sequence of lifting operations and then an isomorphic subgraph is found, we say that is an immersion minor of . There is another way to define the immersion minors, which is equivalent to the lifting operation. We say that is an immersion minor of if there is an injective mapping from node in to node in , where the images of neighboring elements of in are connected by edge-disjoint paths. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$

The immersion minor relation is a quasi-order on the set of finite graphs , and therefore the minor theorem of Robertson and Seymour holds for immersion minors.

When drawing graphs, immersion minors are created as planarizations of non-planar graphs: An immersion minor can be formed from a drawing of a graph in the plane with intersection points by replacing each intersection point with a new node and also dividing each crossed edge into a path . This allows drawing methods for planar graphs to be extended to non-planar graphs.

Odd Minors

An alternative and equivalent definition of minors is that a minor of is when the nodes of can be represented by a collection of vertex-disjoint subtrees of such that when two nodes in are adjacent , an edge with its terminal nodes in the corresponding two trees in exists. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$

An odd minor restricts this definition by adding parity constraints to these subtrees. When represented by a collection of subtrees of as above , an odd minor of is if it is possible to assign the nodes of two colors so that each edge from within a subtree is correctly colored because its terminal nodes are different colors, and every edge of that represents a neighborhood between two subtrees is monochromatic, that is, both end nodes have the same color. Unlike the usual kind of minors, graphs with forbidden odd minors are not necessarily thin. The presumption of Hadwiger that k-chromatic graphs necessarily complete graphs included with n vertices as minors, odd minors has also been studied from the viewpoint. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Bipartite Minors

Another extension of the definition of minors is the concept of a bipartite minor, which creates a bipartite graph when the original graph is bipartite. A graph is a bipartite graph Minor another when out can be obtained by nodes removed edges away and edges contractions are performed along a peripheral cycle have the graph the distance from each other two. One form of Wagner's theorem applies to bipartite minors: A bipartite graph is a planar graph if and only if it does not have the completely bipartite graph as a bipartite minor. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle K_{3,3}}$

literature

• Lutz Volkmann: Foundations of the graph theory. Springer (Vienna) 1996, ISBN 3-211-82774-9 .
  Newer online version: graphs on all corners and edges. (PDF; 3.7 MB).
• Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages, online version ).

Web links

• Eric W. Weisstein : Graph Minor . In: MathWorld (English).
• {{{Author}}}: Minor of a graph . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).

Individual evidence

1. ^ Guoli Ding: Excluding a long double path minor . In: Journal of Combinatorial Theory . 66, No. 1, 1996, pp. 11-23. doi : 10.1006 / jctb.1996.0002 .
2. ↑ Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, Petra Mutzel: Handbook of Graph Drawing and Visualization . In: CRC Press, Boca Raton, FL . 2014.
3. ↑ Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed: The disjoint paths problem in quadratic time . In: Journal of Combinatorial Theory . 102, No. 2, March 2012, pp. 424-435. doi : 10.1016 / j.jctb.2011.07.004 .
4. ↑ Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta: On the odd-minor variant of Hadwiger's conjecture . In: Journal of Combinatorial Theory . 99, No. 1, 2009, pp. 20-29. doi : 10.1016 / j.jctb.2008.03.006 .
5. ^ Maria Chudnovsky, Gil Kalai, Eran Nevo, Isabella Novik, Paul Seymour: Bipartite minors . In: Journal of Combinatorial Theory . 116, 2016, pp. 219-228. arxiv : 1312.0210 . doi : 10.1016 / j.jctb.2015.08.001 .