Graph minor
In
The theory of graph minors began with
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's conjecture relating the inability to 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 that removes an edge from a graph while simultaneously merging the two vertices it used to connect. An
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
In other contexts (such as with the study of pseudoforests) 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.[5]
A function f is referred to as "minor-monotone" if, whenever H is a minor of G, one has f(H) ≤ f(G).
Example
In the following example, graph H is a minor of 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):
Major results and conjectures
It is straightforward to verify that the graph minor
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 that 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 embedded on surfaces of bounded genus. Thus, their theory establishes fundamental connections between graph minors and topological embeddings of graphs.[8]
For any graph H, the simple H-minor-free graphs must be
The
Minor-closed graph families
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
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 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.[2] The best-known example of a characterization of this type is Wagner's theorem characterizing the planar graphs as the graphs having neither K5 nor K3,3 as minors.[1]
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
Variations
Topological minors
A graph H is called a topological minor of a graph G if a
The topological minor relation is not a well-quasi-ordering on the set of finite graphs[23] 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.[24]
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 planarizations of 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.[25]
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. 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.[26] They also allow the theory of graph minors to be extended to classes of graphs such as the 1-planar graphs that are not closed under taking minors.[27]
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.[28] The Hadwiger conjecture, that k-chromatic graphs necessarily contain k-vertex complete graphs as minors, has also been studied from the point of view of odd minors.[29]
A different parity-based extension of the notion of graph minors is the concept of a
Algorithms
The problem of
In the case where H is a fixed planar graph, then we can test in linear time in an input graph G whether H is a minor of G.[34] In cases where H is not fixed, faster algorithms are known in the case where G is planar.[35]
Notes
- ^ a b Lovász (2006), p. 77; Wagner (1937a).
- ^ a b Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).
- ^ a b Robertson & Seymour (1995).
- ^ a b Fellows & Langston (1988).
- ^ 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 K3 as a minor", true only for simple graphs.
- ^ Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson & Seymour (2004).
- ^ Lovász (2006), p. 76.
- ^ Lovász (2006), pp. 80–82; Robertson & Seymour (2003).
- ^ Mader (1967).
- ^ Kostochka (1982); Kostochka (1984); Thomason (1984); Thomason (2001).
- ^ Alon, Seymour & Thomas (1990); Plotkin, Rao & Smith (1994); Reed & Wood (2009).
- ^ Grohe (2003)
- ^ Hadwiger (1943).
- ^ Robertson, Seymour & Thomas (1993).
- ^ Thomas (1999); Pegg (2002).
- ^ Robertson & Seymour (1983).
- ^ Lovász (2006), Theorem 9, p. 81; Robertson & Seymour (1986).
- ^ Eppstein (2000); Demaine & Hajiaghayi (2004).
- ^ Robertson & Seymour (1993); Demaine, Hajiaghayi & Thilikos (2002).
- ^ Wagner (1937a); Wagner (1937b); Hall (1943).
- ^ Diestel 2005, p. 20
- ^ Diestel 2005, p. 22
- ^ Ding (1996).
- ^ Błasiok et al. (2015)
- ^ Buchheim et al. (2014).
- ^ Nešetřil & Ossona de Mendez (2012).
- ^ Nešetřil & Ossona de Mendez (2012), pp. 319–321.
- S2CID 17385711.
- MR 2467815.
- S2CID 14571660.
- ^ Kawarabayashi, Kobayashi & Reed (2012).
- .
- ^ Bodlaender, Hans L. (1993). "A Tourist Guide through Treewidth" (PDF). Acta Cybernetica. 11: 1–21. See end of Section 5.
- ^ Bodlaender, Hans L. (1993). "A Tourist Guide through Treewidth" (PDF). Acta Cybernetica. 11: 1–21. First paragraph after Theorem 5.3
- S2CID 6204674.
References
- MR 1065053.
- Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile (2015), Induced minors and well-quasi-ordering, Bibcode:2015arXiv151007135B.
- .
- Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra (2014), "Crossings and planarization", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL.
- S2CID 390856.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
- Ding, Guoli (1996), "Excluding a long double path minor", MR 1368512.
- S2CID 3172160.
- S2CID 16587284.
- S2CID 11751235.
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich, 88: 133–143.
- Hall, Dick Wick (1943), "A note on primitive skew curves", .
- Kostochka, Alexandr V. (1982), "The minimum Hadwiger number for graphs with a given mean degree of vertices", Metody Diskret. Analiz. (in Russian), 38: 37–58.
- Kostochka, Alexandr V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica, 4 (4): 307–316, S2CID 15736799.
- .
- Mader, Wolfgang (1967), "Homomorphieeigenschaften und mittlere Kantendichte von Graphen", Mathematische Annalen, 174 (4): 265–268, S2CID 120261785.
- MR 2920058.
- .
- Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions", Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994), pp. 462–470.
- S2CID 760001.
- .
- Robertson, Neil; Seymour, Paul D. (1993), "Excluding a graph with one crossing", in Robertson, Neil; Seymour, Paul (eds.), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 669–675.
- .
- .
- .
- S2CID 9608738.
- MR 1725004.
- Thomason, Andrew (1984), "An extremal function for contractions of graphs", S2CID 124801301.
- Thomason, Andrew (2001), "The extremal function for complete minors", .
- S2CID 123534907.
- Wagner, Klaus (1937b), "Über eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik, 2: 280–285.