Community hub
Recent from talks
Contribute something
Nothing was collected or created yet.
Graph minor
View on WikipediaIn graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3.[1] The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.[2] For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time;[3] together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.[4]
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
[edit]An edge contraction is an operation that 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 minors. In this context, it is common to assume that all graphs are connected, with self-loops and multiple edges allowed (that is, they are multigraphs 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 of a graph unchanged, and edge contractions always reduce the rank by one.
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
[edit]In the following example, graph H is a minor of graph G:
H. 
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
[edit]It is straightforward to verify that the graph minor relation forms a partial order on the isomorphism classes of finite undirected graphs: it is 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 and Paul Seymour states that this partial order is actually a well-quasi-ordering: if an infinite list (G1, G2, …) of finite graphs is given, then there always exist two indices i < j such that Gi is a minor of Gj. Another equivalent way of stating this is that any set of graphs can have only a finite number of minimal elements under the minor ordering.[6] 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.[7]
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 sparse, which means that the number of edges is less than some constant multiple of the number of vertices.[9] More specifically, if H has h vertices, then a simple n-vertex simple H-minor-free graph can have at most edges, and some Kh-minor-free graphs have at least this many edges.[10] Thus, if H has h vertices, then H-minor-free graphs have average degree and furthermore degeneracy . 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 vertices whose removal splits G into two (possibly disconnected) subgraphs with at most 2n⁄3 vertices per subgraph.[11] Even stronger, for any fixed H, H-minor-free graphs have treewidth .[12]
The 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 proper coloring with k – 1 colors.[13] The case k = 5 is a restatement of the four color theorem. The Hadwiger conjecture has been proven for k ≤ 6,[14] but is unknown in the general case. 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 bridgeless 3-regular graph that requires four colors in an edge coloring must have the Petersen graph as a minor.[15]
Minor-closed graph families
[edit]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 embedding of a graph on a fixed topological surface, neither the removal of edges nor the contraction of edges can increase the 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 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 pathwidth if and only if its forbidden minors include a forest,[16] F has bounded tree-depth if and only if its forbidden minors include a disjoint union of path graphs, F has bounded treewidth if and only if its forbidden minors include a planar graph,[17] and F has bounded local treewidth (a functional relationship between 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).[18] If H can be drawn in the plane with only a single crossing (that is, it has 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.[19] For instance, both K5 and K3,3 have crossing number one, and as Wagner showed the K5-free graphs are exactly the 3-clique-sums of planar graphs and the eight-vertex Wagner graph, while the K3,3-free graphs are exactly the 2-clique-sums of planar graphs and K5.[20]
Variations
[edit]Topological minors
[edit]A graph H is called a topological minor of a graph G if a subdivision of H is isomorphic to a subgraph of G.[21] Every topological minor is also a minor. The converse however is not true in general (for instance the complete graph K5 in the Petersen graph is a minor but not a topological one), but holds for graph with maximum degree not greater than three.[22]
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
[edit]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
[edit]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
[edit]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
[edit]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 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 K3,3 as a bipartite minor.[30]
Algorithms
[edit]The problem of 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(n3), where n is the number of vertices in G and the big O notation hides a constant that depends superexponentially on H;[3] since the original Graph Minors result, this algorithm has been improved to O(n2) time.[31] Thus, by applying the polynomial time algorithm for testing whether a given graph contains any of the forbidden minors, it is theoretically possible to recognize the members of any minor-closed family in polynomial time. This result is not used in practice since the hidden constant is so huge (needing three layers of Knuth's up-arrow notation to express) as to rule out any application, making it a galactic algorithm.[32] Furthermore, in order to apply this result constructively, it is necessary to know what the forbidden minors of the graph family are.[4] In some cases, the forbidden minors are known, or can be computed.[33]
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
[edit]- ^ 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.
- ^ Kawarabayashi, Ken-ichi; Reed, Bruce; Wollan, Paul (2011), "The graph minor algorithm with parity conditions", 52nd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, pp. 27–36, doi:10.1109/focs.2011.52, ISBN 978-0-7695-4571-4, S2CID 17385711.
- ^ Geelen, Jim; Gerards, Bert; Reed, Bruce; Seymour, Paul; Vetta, Adrian (2009), "On the odd-minor variant of Hadwiger's conjecture", Journal of Combinatorial Theory, Series B, 99 (1): 20–29, doi:10.1016/j.jctb.2008.03.006, MR 2467815.
- ^ Chudnovsky, Maria; Kalai, Gil; Nevo, Eran; Novik, Isabella; Seymour, Paul (2016), "Bipartite minors", Journal of Combinatorial Theory, Series B, 116: 219–228, arXiv:1312.0210, doi:10.1016/j.jctb.2015.08.001, MR 3425242, S2CID 14571660.
- ^ Kawarabayashi, Kobayashi & Reed (2012).
- ^ Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303. CiteSeerX 10.1.1.114.3864. doi:10.1016/0196-6774(87)90043-5.
- ^ 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
- ^ Adler, Isolde; Dorn, Frederic; Fomin, Fedor V.; Sau, Ignasi; Thilikos, Dimitrios M. (2012-09-01). "Fast Minor Testing in Planar Graphs" (PDF). Algorithmica. 64 (1): 69–84. doi:10.1007/s00453-011-9563-9. ISSN 0178-4617. S2CID 6204674.
References
[edit]- Alon, Noga; Seymour, Paul; Thomas, Robin (1990), "A separator theorem for nonplanar graphs", Journal of the American Mathematical Society, 3 (4): 801–808, doi:10.2307/1990903, JSTOR 1990903, MR 1065053.
- Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile (2015), Induced minors and well-quasi-ordering, arXiv:1510.07135, Bibcode:2015arXiv151007135B.
- Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph", European Journal of Combinatorics, 1 (3): 195–199, doi:10.1016/s0195-6698(80)80001-1.
- 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.
- Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica, 40 (3): 211–215, doi:10.1007/s00453-004-1106-1, S2CID 390856.
- Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2002), "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor", Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), Lecture Notes in Computer Science, vol. 2462, Springer-Verlag, pp. 67–80, doi:10.1007/3-540-45753-4_8, ISBN 978-3-540-44186-1
- 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", Journal of Combinatorial Theory, Series B, 66 (1): 11–23, doi:10.1006/jctb.1996.0002, MR 1368512.
- Eppstein, David (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica, 27 (3): 275–291, arXiv:math.CO/9907126, doi:10.1007/s004530010020, MR 1759751, S2CID 3172160.
- Fellows, Michael R.; Langston, Michael A. (1988), "Nonconstructive tools for proving polynomial-time decidability", Journal of the ACM, 35 (3): 727–739, doi:10.1145/44483.44491, S2CID 16587284.
- Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica, 23 (4): 613–632, arXiv:math/0001128, doi:10.1007/s00493-003-0037-9, 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", Bulletin of the American Mathematical Society, 49 (12): 935–936, doi:10.1090/S0002-9904-1943-08065-2.
- Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (March 2012), "The disjoint paths problem in quadratic time", Journal of Combinatorial Theory, Series B, 102 (2): 424–435, doi:10.1016/j.jctb.2011.07.004
- 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, doi:10.1007/BF02579141, S2CID 15736799.
- Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8.
- Mader, Wolfgang (1967), "Homomorphieeigenschaften und mittlere Kantendichte von Graphen", Mathematische Annalen, 174 (4): 265–268, doi:10.1007/BF01364272, S2CID 120261785.
- Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 62–65, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
- Pegg, Ed Jr. (2002), "Book Review: The Colossal Book of Mathematics" (PDF), Notices of the American Mathematical Society, 49 (9): 1084–1086.
- 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.
- Reed, Bruce; Wood, David R. (2009), "A linear-time algorithm to find a separator in a graph excluding a minor", ACM Transactions on Algorithms, 5 (4) 39, doi:10.1145/1597036.1597043, S2CID 760001.
- Robertson, Neil; Seymour, Paul (1983), "Graph minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5.
- Robertson, Neil; Seymour, Paul D. (1986), "Graph minors. V. Excluding a planar graph", Journal of Combinatorial Theory, Series B, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4
- 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.
- Robertson, Neil; Seymour, Paul D. (1995), "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B, 63 (1): 65–110, doi:10.1006/jctb.1995.1006.
- Robertson, Neil; Seymour, Paul D. (2003), "Graph Minors. XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X.
- Robertson, Neil; Seymour, Paul D. (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001.
- Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwiger's conjecture for K6-free graphs" (PDF), Combinatorica, 13 (3): 279–361, doi:10.1007/BF01202354, S2CID 9608738.
- Thomas, Robin (1999), "Recent excluded minor theorems for graphs", Surveys in combinatorics, 1999 (Canterbury) (PDF), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge: Cambridge Univ. Press, pp. 201–222, MR 1725004.
- Thomason, Andrew (1984), "An extremal function for contractions of graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 95 (2): 261–265, Bibcode:1983MPCPS..95..261T, doi:10.1017/S0305004100061521, S2CID 124801301.
- Thomason, Andrew (2001), "The extremal function for complete minors", Journal of Combinatorial Theory, Series B, 81 (2): 318–338, doi:10.1006/jctb.2000.2013.
- Wagner, Klaus (1937a), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann., 114: 570–590, doi:10.1007/BF01594196, S2CID 123534907.
- Wagner, Klaus (1937b), "Über eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik, 2: 280–285.
External links
[edit]Graph minor
View on GrokipediaCore Concepts
Definitions
In graph theory, a graph is a minor of a graph if a graph isomorphic to can be obtained from by a sequence of vertex deletions, edge deletions, and edge contractions.[4] This definition applies to simple undirected graphs, which have no loops or multiple edges between the same pair of vertices.[4] Vertex deletion removes a vertex from along with all edges incident to it. Edge deletion removes a single edge while preserving its endpoints. Edge contraction merges two adjacent vertices and into a single vertex, whose incident edges are the union of those originally incident to or ; any resulting self-loops or multiple edges are then deleted to maintain simplicity.[4] The minor relation is denoted when is a minor of , forming a partial order on the set of finite graphs up to isomorphism.[4] Equivalently, indicates the same relation. A model of the minor in consists of vertex-disjoint connected subgraphs of , called branch sets, one for each vertex of ; for every edge in between vertices and , there is an edge in between the corresponding branch sets and . These branch sets capture the structure obtained after contractions, with edges in realized by direct connections or paths within .[4]Basic Properties
The minor relation on the set of finite undirected graphs, considered up to isomorphism, forms a partial order. This relation is reflexive, as every graph is a minor of itself, obtained without any deletions or contractions. It is transitive: if is a minor of and is a minor of , then is a minor of , since the sequence of edge deletions, vertex deletions, and edge contractions that yield from can be followed by those that yield from . The relation is also antisymmetric, meaning that if has as a minor and has as a minor, then and are isomorphic. A family of graphs is minor-closed if it contains all minors of its members; that is, whenever belongs to the family and is a minor of , then also belongs to the family. This closure property follows directly from the definition of the minor relation and ensures that such families are stable under the operations of deletion and contraction. Minor-closed families play a central role in graph theory, as many natural graph properties—such as planarity or bounded tree-width—are preserved under taking minors. One key aspect of minor-closed families is their characterization via forbidden minors: a family consists of all graphs that do not contain any graph from a fixed (possibly infinite) set as a minor.[5] This setup provides a structural description, where membership in the family is determined by the absence of certain "obstructing" minors; a foundational result later shows that for any minor-closed family, this set of forbidden minors can be taken to be finite, though the proof of finiteness lies beyond basic properties. Minors also exhibit size relations relative to their host graphs. Specifically, if is a minor of , then and , since each operation of edge deletion, vertex deletion, or edge contraction either preserves or strictly decreases the number of vertices and edges.Illustrative Examples
Introductory Examples
To illustrate the concept of a graph minor, consider path graphs, which provide a simple starting point. A path graph on vertices is a connected graph consisting of a sequence of edges forming a chain without branches or cycles. Any shorter path with is a minor of , obtained by deleting the unnecessary vertices and their incident edges from the ends or middle of the path. This process preserves the linear structure while reducing the length, demonstrating how vertex and edge deletions can yield minors. Edge contractions are not typically needed here, as deletions suffice, but in more general cases, they allow merging adjacent vertices along the path to shorten it further if desired.[1][6] Cycle minors offer another accessible example, highlighting the role of edge deletions. The cycle graph , a 4-vertex cycle with edges forming a square, is a minor of the complete graph on 4 vertices, where every pair of vertices is connected. To obtain from , delete the two diagonal edges that cross the square; the remaining four edges form exactly as a subgraph, which is trivially a minor since no contractions or vertex deletions are required beyond that. This shows how minors can simplify dense graphs by removing excess connections while retaining a cyclic structure.[1][6] Trees as minors emphasize the use of edge contractions to eliminate cycles. A tree , being an acyclic connected graph, can be obtained as a minor from a more complex graph that contains as a spanning subgraph with additional cycles by contracting edges within those cycles. For instance, if has cycles attached to the branches of , contracting each cycle's edges merges its vertices into a single vertex, effectively removing the cycle and preserving the tree's branch structure. This process, repeated as needed, transforms into without introducing loops or multiple edges between the same pairs.[1][3] For a step-by-step visualization of contractions, consider obtaining the complete graph (a triangle) as a minor from the larger complete graph . Start with , which has vertices and all six possible edges. Select one edge, say between and , and contract it: merge and into a new vertex , remove the self-loop at , and replace any parallel edges with singles (though none arise here). The resulting graph now has vertices with edges -, -, and -, forming exactly . This sequence illustrates how contractions reduce vertex count while maintaining completeness.[6][1] A key limitation arises with disconnected graphs, underscoring that minors respect component boundaries. If a graph is disconnected with components of sizes at most vertices, then cannot have a connected minor with more than vertices, as any minor operation—deleting edges or vertices, or contracting edges—applies separately within each component and cannot bridge disconnected parts to form a larger connected structure. For example, two isolated s (each a single edge) have no connected minor larger than , since contractions within components yield at most paths or single vertices per part.[1][6]Advanced Examples
One prominent example of a complete graph minor in non-planar graphs is the presence of as a minor in the Petersen graph, obtained through a sequence of edge contractions that merge vertices into five branch sets, each corresponding to a vertex in , while ensuring complete connectivity between them via the original edges.[6] The Petersen graph, despite its 3-regular structure and girth of 5 (preventing a subgraph), exhibits this minor, highlighting how contractions can create denser structures in highly connected (3-vertex-connected) graphs.[7] Kuratowski's graphs provide explicit constructions for forbidden minors in planarity: and . The utility graph, isomorphic to , directly embeds as a minor since it is the graph itself, with its three vertices on each side of the bipartition fully connected across partitions, demonstrating non-planarity through this bipartite complete structure.[8] Similarly, embeds as a minor in non-planar graphs like the Petersen graph, where branch sets are formed by partitioning vertices and contracting paths or edges to achieve the complete 5-vertex connectivity, as no planar graph can contain such a minor.[6] These constructions, rooted in Kuratowski's 1930 characterization of non-planar graphs via subdivisions (equivalent to minors for these graphs), illustrate how explicit vertex partitions and contractions reveal forbidden structures.[9] The Petersen graph further exemplifies advanced minor properties, containing both and as minors despite lacking a subdivision of (though containing one of ) due to its symmetry and degree constraints; for , deletions followed by contractions yield the bipartite complete graph, underscoring its role as a minimal non-planar example with high connectivity.[7] In graphs embeddable on the torus, grid minors offer insight into structural complexity beyond planarity. For instance, a graph on the torus with sufficient face-width contains a toroidal -grid as a minor, where the toroidal grid wraps edges around the surface; large such grids (e.g., ) are non-planar, as they violate Euler's formula with vertices and edges exceeding , thus indicating the host graph's non-planarity through this minor.[10] This builds intuition for how surface embeddings allow denser minor structures compared to planar graphs.Key Theorems and Conjectures
Wagner's Theorem
Wagner's theorem provides a characterization of planar graphs in terms of forbidden minors: a finite graph is planar if and only if it contains neither the complete graph nor the complete bipartite graph as a minor.[11] This result was established by Klaus Wagner in 1937, building on Kazimierz Kuratowski's earlier 1930 theorem that characterizes planarity via forbidden subdivisions.[11] The necessity of the condition follows from the fact that the class of planar graphs is closed under minors, combined with the non-planarity of and . For , with 5 vertices and 10 edges, Euler's formula for planar graphs implies that a simple connected planar graph on vertices satisfies , but here , yielding a contradiction.[12] For , which is bipartite with 6 vertices and 9 edges, the corresponding bound for bipartite planar graphs is , but ; alternatively, any drawing requires at least one crossing due to the bipartite structure and edge connectivity.[12] Thus, no planar graph can have these as minors. The sufficiency is proved by induction on the number of vertices. For the base case of small graphs, planarity is direct. For larger graphs, consider 3-connected components: by Tutte's theorem, there exists an edge whose contraction yields a smaller 3-connected graph, which is planar by the inductive hypothesis; the original graph is then planar by adding back the edge without crossings.[13] Non-3-connected cases reduce to gluing planar subgraphs along vertices or edges, preserving planarity.[13] Wagner's theorem is equivalent to Kuratowski's theorem, as the notions of subdivision and minor are interreducible for these forbidden configurations: any subdivision of or contracts to the graph itself as a minor, and conversely, any such minor can be "expanded" by subdividing edges to form a subdivision subgraph.[12] This equivalence highlights that minors generalize subdivisions, providing a more structural characterization.[12] A key implication is that planarity is defined by a finite set of forbidden minors—specifically, just two—demonstrating the minor-closed nature of the planar graph family in a concrete and minimal way.[11]Robertson-Seymour Theorem
The Robertson–Seymour theorem, also known as the graph minors theorem, asserts that the collection of all finite undirected graphs, partially ordered by the relation of one graph being a minor of another, forms a well-quasi-order. In this context, a well-quasi-order on a set is a quasi-order with no infinite descending chains (sequences where each element is strictly less than the previous) and no infinite antichains (subsets where no two elements are comparable).[14] This property implies that in any infinite sequence of finite graphs, there exist indices such that the -th graph is a minor of the -th graph.[14] A fundamental corollary of the theorem is that every minor-closed family of graphs—meaning a family closed under taking minors and subgraphs—has a finite set of forbidden minors that completely characterizes it: a graph belongs to the family if and only if it contains none of these forbidden graphs as a minor.[15] This finite characterization generalizes earlier results, such as Wagner's theorem for planar graphs, to arbitrary minor-closed families.[15] The theorem emerged from an extensive research project by Neil Robertson and Paul Seymour, spanning 20 papers published between 1983 and 2004, which collectively resolved Wagner's 1937 conjecture that the minor relation on finite graphs is well-quasi-ordered.[15] The proof, detailed primarily in the series' later installments (notably Graph Minors XVI and XX), builds on foundational work in the earlier papers establishing structural properties of graphs excluding specific minors.[14] At its core, the proof employs tree decompositions—hierarchical representations of graphs that capture their connectivity via tree-structured bags of vertices—to derive structure theorems for graphs excluding a fixed minor . These theorems describe such graphs as being built via controlled operations (clique-sums and extensions) from simpler components, such as subgraphs embeddable on surfaces or with bounded tree-width, ensuring the absence of infinite bad sequences under the minor order.[15] The approach culminates in showing that the set of all finite graphs excluding is well-quasi-ordered, extending inductively to the full result.[14] Among the theorem's significant corollaries are algorithmic implications: for any fixed finite set of forbidden minors, there exists a cubic-time algorithm () to determine whether a given -vertex graph belongs to the corresponding minor-closed family.[15] Additionally, the well-quasi-ordering precludes infinite minor-closed antichains, meaning no infinite collection of graphs exists where no one is a minor of another.[14]Hadwiger's Conjecture
Hadwiger's conjecture, proposed by Hugo Hadwiger in 1943, states that every graph without a complete graph as a minor is -colorable for any integer .[16] Equivalently, the conjecture asserts that the Hadwiger number , defined as the largest integer such that is a minor of the graph , satisfies , where is the chromatic number of . This formulation links the structural property of excluding clique minors to the graph's coloring requirements.[17] The conjecture arose as an attempt to generalize the four-color theorem, which asserts that planar graphs are 4-colorable and equivalently that graphs without minors are 4-colorable, a result later proved in 1976.[16] Hadwiger himself verified the conjecture for , noting its equivalence to the four-color theorem for via Wagner's earlier work on planar graphs and -minor-free graphs.[18] For , Robertson, Seymour, and Thomas established the result in 1993 by showing that every -minor-free graph is 5-colorable, building on structural characterizations from graph minor theory.[18] These cases confirm the conjecture for , but despite extensive searches, no counterexamples have been found for larger , leaving it open for .[16] Partial progress includes connections to the stronger but disproved Hajós conjecture from 1961, which claimed that graphs with chromatic number at least contain a subdivision (a topological minor); Hadwiger's version weakens this by allowing contractions, providing a potential path to colorings via minor exclusions.[19] Additionally, graphs without minors exhibit bounded degeneracy, as every such graph has average degree at most , implying they are -colorable by greedy coloring on degenerate orderings. This bound, independently proved by Kostochka in 1984 and Thomason in 1984, establishes that Hadwiger's conjecture holds asymptotically up to a logarithmic factor. As of 2025, the conjecture remains unresolved, with no full proof or counterexample identified, though algorithmic advances in finding large clique minors offer approximations for computing relative to .[20] Recent improvements refine the degeneracy bound to -colorability for -minor-free graphs, narrowing the gap toward the conjectured linear bound.[21]Other Significant Results
One significant line of research in graph minor theory concerns the extremal function ex(n, H), which denotes the maximum number of edges in an n-vertex graph without H as a minor. Mader established that for any fixed graph H, ex(n, H) = O(n), proving that there exists a constant c(H) such that any graph with more than c(H) n edges contains H as a minor. For the specific case of complete graphs, Kostochka and Thomason independently showed that ex(n, K_r) \sim \frac{r \sqrt{\log r}}{2 \sqrt{2}} n for large r, providing an asymptotic upper bound of O(r \sqrt{\log r} , n).[22] This linear dependence on n holds for fixed r as well, with exact values known for small r; for example, ex(n, K_3) = n-1, achieved by forests.[22] Applications of Szemerédi's regularity lemma have yielded improved bounds on the density of minors in dense graphs. The lemma partitions the vertex set into equitable parts where most bipartite subgraphs between parts are regular, enabling the extraction of dense substructures that force minors. In the 1990s, Thomassen contributed to the study of embeddings and their relation to minors, particularly in characterizing linkless embeddings of graphs in 3-space. A linkless embedding is one where no two disjoint cycles form a nontrivial link. Thomassen showed that the class of graphs admitting linkless embeddings is minor-closed, and subsequent work by Robertson, Seymour, and Thomas fully characterized it by excluding the seven graphs of the Petersen family as minors; these are the forbidden minors for flat embeddings, a stronger condition where every cycle bounds a disk disjoint from the graph. Thomassen's results on highly connected sets and excluded grid theorems further linked embedding properties to minor exclusions. The duplication lemma provides a construction tool for graphs with prescribed minor properties by allowing vertex duplication while preserving minor-closed characteristics. Specifically, duplicating a vertex—replacing it with two adjacent vertices connected to its neighbors—maintains the absence of certain forbidden minors in families like perfect graphs or planar graphs, facilitating the building of extremal examples without introducing unwanted minors. This lemma is instrumental in inductive constructions for proving bounds on minor densities. Recent advances post-2020 have improved approximations for the Hadwiger number η(G), the size of the largest complete minor in G. Norin's 2022 ICM survey highlights that K_t-minor-free graphs are O(t \log \log t)-colorable, advancing towards Hadwiger's conjecture by reducing the logarithmic factor from previous O(t (\log t)^{1/4 + \epsilon}) bounds. For graphs with small clique number ω(G) \leq \sqrt{\log t} / (\log \log t)^2, such graphs are O(t)-colorable, supporting linear approximations in restricted cases. While semidefinite programming has been applied to related coloring relaxations via the Lovász theta function, providing O(\sqrt{n})-approximations for chromatic number that indirectly bound η(G) via the conjecture, direct SDP methods for η(G) remain exploratory in surveys up to 2025.Minor-Closed Graph Families
Characterization and Structure
A proper minor-closed family of graphs—meaning a family closed under taking minors but not containing all graphs—admits a finite characterization by forbidden minors. Specifically, the Robertson–Seymour theorem establishes that every such family is defined by excluding a finite set of graphs as minors, allowing the family to be precisely described as the graphs avoiding these finitely many obstructions.[23] The structure theorem for graphs excluding a fixed minor provides a decomposition that reveals the hierarchical organization of such graphs. Any -minor-free graph can be built via clique-sums from subgraphs of bounded treewidth, graphs embeddable on a fixed surface, apex graphs (where removing a single vertex yields a planar graph), and vortex structures (bounded-degree expansions of cycles). This decomposition highlights the bounded complexity and layered nature of minor-closed classes.[24] Within this framework, apex graphs play a key role in capturing near-planar structures, while layered families—those with bounded layered treewidth—emerge as essential building blocks for broader minor-closed classes. A minor-closed family has bounded layered treewidth if and only if it excludes some apex-forest as a minor, enabling recursive constructions that maintain structural uniformity.[25] For families defined by a fixed finite set of forbidden minors, membership testing is possible in polynomial time, as minor containment for each fixed obstruction can be decided efficiently, though the degree of the polynomial depends on the size of the forbidden graphs.[26] The well-quasi-ordering property of the minor relation, central to the Robertson–Seymour theorem, forbids infinite antichains in the poset of finite graphs ordered by minors, ensuring that minor-closed families cannot contain infinite incomparable subcollections.[23]Prominent Examples
Planar graphs form one of the most prominent minor-closed families, characterized precisely as those graphs that exclude both the complete graph and the complete bipartite graph as minors. This finite forbidden minor characterization, established by Wagner in 1936, parallels Kuratowski's earlier theorem for subdivisions but applies directly to the minor relation.[27] A proper subclass of planar graphs, outerplanar graphs—those embeddable in the plane with all vertices on the outer face—are characterized by forbidding and as minors. This two-minor obstruction was identified by Sysło, providing a structural basis for efficient recognition and embedding algorithms within this family.[28] Series-parallel graphs, which arise in network theory and have treewidth at most 2, are exactly the graphs excluding as a minor. This single forbidden minor captures their recursive construction via series and parallel compositions starting from edges, enabling linear-time optimization for many problems like shortest paths in such networks.[29] The family of forests, consisting of graphs without cycles, is minor-closed and forbids only (a triangle) as a minor. Any contraction or deletion in a forest preserves acyclicity, making the unique obstruction that introduces a cycle via minor operations.[1] Toroidal graphs, embeddable on the torus surface (genus 1), form a minor-closed family with a finite set of forbidden minors, as guaranteed by the Robertson-Seymour theorem; the complete set remains unknown, but contains at least 17,523 graphs.[30] This complexity underscores the challenges in fully listing obstructions for higher-genus embeddings. Graphs excluding an grid as a minor represent families with bounded treewidth, a cornerstone of structural graph theory. The grid minor theorem states that any graph with treewidth exceeding a polynomial in (with the current best bound \tilde{O}(r^9) as of 2025) contains an grid minor, linking minor exclusions to decomposability and algorithmic tractability.[31]Variants of Graph Minors
Topological Minors
A graph is a topological minor of a graph if contains a subdivision of as a subgraph, meaning that can be obtained from a subgraph of by replacing each edge with a path of arbitrary length greater than or equal to 1, where the paths are internally vertex-disjoint except at the endpoints corresponding to vertices of .[32] This concept arises from the operation of subdividing edges, which is a special case of edge contraction where only paths of length greater than 1 are contracted to single edges. Every topological minor of a graph is also a minor, since subdividing edges and then contracting them back recovers the original structure through allowed minor operations like deletions and contractions.[32] However, the converse does not hold: a graph may contain as a minor without containing a subdivision of as a subgraph, particularly when has vertices of degree greater than 3 and the minor arises from contractions that merge multiple edges incident to a single vertex. For instance, containing as a topological minor requires the existence of five vertices connected by pairwise internally vertex-disjoint paths, implying that the graph is 4-connected, whereas a -minor does not necessarily impose such strong connectivity requirements.[32] For complete graphs, the presence of as a topological minor admits a precise characterization: a graph contains as a topological minor if and only if there exist distinct vertices in , each of degree at least , such that between every pair of these vertices there is an internally vertex-disjoint path. This condition ensures the branch vertices and subdivided edges form the required subdivision, and it aligns with connectivity criteria derived from Menger's theorem for multiple disjoint paths.[32] Topological minors play a key role in applications involving embeddings and structural graph properties. In particular, the Robertson–Seymour–Thomas theorem characterizes graphs admitting linkless embeddings in 3-dimensional space—embeddings where no two cycles are linked—precisely as those excluding any of the seven graphs in the Petersen family as topological minors. This result connects topological minors to geometric and topological constraints in 3-space, with implications for knot theory, where linkless configurations avoid knotted or linked substructures analogous to those in classical knot diagrams. In contrast to standard minor-closed graph families, which are characterized by finite sets of forbidden minors by the Robertson–Seymour graph minor theorem, topological-minor-closed families can require infinite sets of forbidden topological minors for their characterization. For example, certain structurally restricted classes, such as those embeddable on specific surfaces beyond the plane, may exclude infinitely many minimal topological obstructions due to the well-quasi-ordering properties differing under the topological minor relation.Induced Minors
An induced minor of a graph is a graph that can be obtained by first selecting an induced subgraph of and then contracting a subset of its edges.[33] Equivalently, arises from via a sequence of vertex deletions followed by edge contractions.[34] This operation differs from standard minors, as it prohibits edge deletions, thereby avoiding the creation of new edges between non-adjacent vertices during contractions and preserving denser structural information from the original graph.[35] Induced minors form a stricter containment relation than ordinary minors, implying that every induced minor is also a minor, but the converse does not hold.[33] For instance, in chordal graphs, which lack induced cycles of length four or more, the induced-minor relation well-quasi-orders the subclass of graphs with bounded clique number, ensuring no infinite descending chains or antichains under this partial order. This structural rigidity limits the complexity of induced minors in such families compared to broader minor operations. In perfect graph theory, induced minors play a key role in characterizing contraction-perfect graphs, which are those where every induced minor is perfect; these coincide with the perfect graphs themselves, forbidden by odd holes and odd antiholes as induced subgraphs.[36] Similarly, certain induced-minor-closed graph classes, such as those excluding specific forbidden structures like induced subgraphs of bounded treewidth, are -bounded, meaning their chromatic number is controlled by the clique number.[37] Some graph classes admit finite forbidden induced minors, enabling structural characterizations analogous to the Robertson-Seymour theorem for minors. For example, trivially perfect graphs, which are -free as induced subgraphs, form an induced-minor-closed family with a finite set of minimal forbidden induced minors, reflecting their closure under contractions.[36]Immersion Minors
An immersion minor of a graph , also known as an immersion of a graph in , is defined by an injective mapping from the vertices of to distinct vertices of , together with a set of edge-disjoint paths in such that for each edge in , there is a path from to whose internal vertices are not in .[38] This model ensures that the edges of are represented by paths that do not share edges, though they may share internal vertices. Unlike contractions in standard minors, immersions preserve vertex distinctness while allowing path-based edge realizations. Immersion minors form a weaker containment relation compared to topological minors, where the representing paths must also be internally vertex-disjoint from the images of 's vertices; every topological minor is thus an immersion minor, but the converse does not hold.[38] This distinction arises because immersions permit "edge subdivision" via paths that can intersect at non-branch vertices, without allowing vertex splitting as in contractions. The relation is incomparable to the standard minor relation, as neither implies the other in general.[38] In applications, immersion minors extend naturally to directed graphs, where paths respect arc directions, facilitating studies in tournaments and network flow problems such as edge-disjoint path routing.[39] For instance, variants of Hadwiger's conjecture for immersions posit that every graph contains an immersion of the complete graph , linking chromatic number to immersion structure.[40] A seminal result, resolving Nash-Williams' immersion conjecture, establishes that the immersion relation well-quasi-orders finite graphs, implying no infinite antichains under immersion containment.[41] For complete graphs, immersion containment is characterized in terms of minimum degree: a graph with minimum degree at least contains as a strong immersion (where paths are internally disjoint from branch vertices).[38] This bound improves prior estimates and highlights the role of connectivity in forcing immersions. An example occurs in tournaments, where every tournament with minimum out-degree at least (for a constant ) contains a 2-immersion of the complete directed graph on vertices, with paths of length at most 2.[42]Shallow Minors
In graph theory, a graph is an -shallow minor of a graph (for some nonnegative integer ) if can be obtained from a subgraph of by contracting disjoint connected subgraphs, each of radius at most , and then deleting vertices and edges.[43] The radius of a connected subgraph is the smallest eccentricity among its vertices, where the eccentricity of a vertex is the greatest distance to any other vertex in the subgraph.[43] This restriction on the size of contracted subgraphs distinguishes shallow minors from standard graph minors, where contractions can involve arbitrarily large subgraphs.[44] The concept was introduced to facilitate the analysis of graph decompositions and separators, with early work attributing it to explorations in parallel computing and geometric graph classes.[44] Shallow minors provide a framework for studying graph sparsity and structural properties, particularly in classes where full minor exclusions are too restrictive for algorithmic or decomposition purposes. They interpolate between subgraphs (when ) and arbitrary minors (as grows large), allowing approximations of complex minor relations while controlling the "depth" of contractions to preserve local structure.[45] This makes them suitable for metric approximations in graph embeddings, where the bounded radius aligns with notions of coarse geometry, such as Gromov-Hausdorff distances between metric spaces induced by graphs.[45] In sparse graph classes, shallow minors help characterize families with controlled density, enabling efficient algorithms for problems like coloring and embedding that fail under full minor theory. A key property is that classes excluding large shallow minors exhibit improved decompositions, such as small balanced separators of size for graphs excluding a fixed -shallow minor, generalizing Lipton-Tarjan separators for planar graphs.[44] Shallow minors are central to the theory of bounded expansion, where a hereditary graph class has bounded expansion if the maximum average degree of its -shallow minors is bounded by a function , independent of the graph size. Such classes include minor-closed families like planar graphs but extend to broader sparse structures, such as bounded-degree graphs or unit disk graphs, with applications in kernelization and property testing. In applications, shallow minors underpin results for minor-free graphs with bounded expansion, providing polynomial-time algorithms for problems like independent sets and dominating sets in these classes. For instance, graphs excluding a fixed shallow minor admit low-distortion embeddings into minor-free graphs with controlled expansion parameters.[45] Recent developments in the 2020s have leveraged shallow minors to establish product structure theorems for beyond-planar graph classes, such as 1-planar and fan-planar graphs, showing they can be represented as bounded-depth shallow minors of strong products of planar graphs and paths, yielding bounds on parameters like queue-number and treewidth.[46] These hierarchies extend to quasi-tree approximations, where shallow minor exclusions imply structural decompositions resembling tree-like hierarchies with bounded branching.[46]Minors with Additional Constraints
In graph theory, parity minors impose restrictions on the standard minor relation to preserve properties related to even or odd structures, such as cycle lengths modulo 2. Specifically, an odd-minor of a graph is obtained via an odd -expansion, where a subgraph is expanded from using paths and vertices such that a 2-coloring exists on the branch sets, making inter-branch edges monochromatic and ensuring cycle parities are preserved.[47] This relation maintains closure under bipartiteness and planarity, as odd-minors cannot introduce odd cycles into bipartite graphs.[47] Bipartition parities are preserved through the proper 2-coloring of branch sets, which aligns with the global bipartiteness of annotated graphs where odd cycles are limited.[47] The seminal graph minor recognition algorithm has been extended to handle parity conditions, enabling polynomial-time testing for parity -minors, where each cycle in the model in has a specified parity (even or odd length modulo 2).[48] For instance, detecting an odd -minor requires all corresponding cycles in to be odd, which involves modeling with bichromatic tree paths and monochromatic connections between branch sets.[48] These parity constraints facilitate solving problems like finding disjoint odd cycles or odd cliques as minors, with runtime for fixed .[48] Signed minors extend the minor concept to signed graphs, where edges are labeled positive or negative, and operations include edge/vertex deletion, contraction, and re-signing to maintain the sign structure.[49] Contraction in signed graphs merges vertices while adjusting signs to preserve balance, defined as cycles with an even number of negative edges (product of signs equal to +1).[50] This preserves the overall balance of the graph, making signed minors useful for analyzing frustration or balance in social networks and structural graph properties.[51] Classes of signed graphs embeddable on surfaces like the torus or Klein bottle are minor-closed under these operations.[52] Oriented minors apply to directed (oriented) graphs, where a directed graph is an oriented minor of if arises from a subgraph of by contracting directed edges, thereby preserving arc directions in the model.[53] This ensures that paths and cycles in correspond to directed paths in , maintaining the orientation's asymmetry without reversing arcs during contraction.[53] Such minors are crucial for studying directed graph families, like those excluding tournaments or specific digraphs as minors.[54] These constrained minors have applications in matching theory and Pfaffian orientations, where orientations allow efficient perfect matching counts via the Pfaffian determinant. A graph admits a Pfaffian orientation—directing edges so every even central cycle (with a unique perfect matching) has an odd number of forward edges—if it avoids certain forbidden minors.[55] In bipartite graphs, this is equivalent to having no as a matching minor, obtained by bicontracting degree-two vertices in central subgraphs; such avoidance enables polynomial-time matching enumeration.[55] For near-bipartite graphs, Pfaffian status depends on excluding weak matching minors like the cubeplex or twinplex.[55] Additional constraints in minor formation, such as even contractions, impose rules to preserve degree parities or structural evenness in specific families. In perfect graphs, even pair contractions—merging non-adjacent vertices with even-symmetric neighborhoods—yield cliques while preserving perfection, avoiding odd-hole introductions.[36] These rules ensure minors remain in families like Eulerian or bipartite graphs without creating odd cycles.[47]Algorithmic Approaches
Minor Recognition Algorithms
The problem of determining whether a given graph contains a fixed graph as a minor, known as minor recognition, was historically challenging. Prior to the work of Robertson and Seymour, the decidability of this problem for arbitrary fixed remained open, with no general algorithm known, even allowing exponential time; only specific cases, such as testing for small complete graph minors like (triangle detection), could be handled efficiently using methods like matrix multiplication in time where . Early approaches for general relied on brute-force enumeration of potential branch sets—disjoint connected subgraphs in corresponding to vertices of —followed by verification of inter-set connections via edge contractions and deletions, yielding algorithms exponential in both and , such as time via recursive subdivision checks. These methods were impractical beyond very small but provided the foundation for later developments.[6] The Robertson–Seymour theorem resolved this by proving that every minor-closed graph family has a finite set of forbidden minors, implying the existence of a polynomial-time recognition algorithm for any fixed . The general approach constructs such an algorithm using dynamic programming on a tree decomposition of with treewidth bounded by a function derived from the theorem's structure theory; the DP table encodes partial minor models over bags of the decomposition, allowing verification of the full model in time, where the cubic dependence arises from processing subproblems involving edge and vertex operations across the decomposition. This method, detailed across their Graph Minors series, applies the finite obstruction characterization to reduce recognition to checking against the forbidden minors, though the function grows extremely rapidly with , rendering it non-practical for all but tiny . For small fixed , simpler naive implementations achieve time by simulating contractions through iterative subgraph searches—enumerating candidate connected components for each vertex of and testing adjacency via shortest-path computations or union-find structures—avoiding the full decomposition overhead while still leveraging basic minor model definitions.[26] For the special case where is planar, recognition algorithms achieve linear time . Robertson and Seymour's Graph Minors V provides a seminal method exploiting the bounded genus of planar-excluding graphs and embedding techniques to detect minor models via disjoint path routings in surfaces, a result that predates the full theorem and highlights structural advantages for planar . More recent planarity testing algorithms, such as the Boyer–Myrvold framework, enable efficient detection of specific planar minors like or (topological equivalents for planarity) by adding edges and checking for subdivisions in time using DFS-based certification and reduction rules, extending naturally to general fixed planar through similar embedding verifications. These linear-time methods underscore the practical gap between theoretical polynomial bounds and implementable efficiency for structured minors. In practice, the theoretical algorithms' enormous constants limit their use, leading to specialized implementations and heuristics. The SageMath software library includes a graph minor recognition function that computes a minor model by searching for branch sets via iterative contraction and isomorphism checks, suitable for graphs up to hundreds of vertices when is small (e.g., ), often running in seconds for sparse inputs but scaling poorly beyond. For larger sparse graphs and with hundreds of vertices, heuristic approaches dominate, prioritizing speed over guaranteed correctness for applications like network analysis. These tools emphasize conceptual reliance on minor models while adapting dynamic programming elements for real-world scalability.[56]Parameterized Complexity and Fixed-Parameter Tractability
The problem of determining whether a graph contains a fixed graph as a minor can be approached through parameterized complexity, where the parameter is typically the size of , denoted , or the treewidth of . Parameterization by treats as the small input component, allowing algorithms whose running time is for some function and input size . In contrast, parameterization by treewidth of exploits structural sparsity in , even when is arbitrary and part of the input. The -minor containment problem is fixed-parameter tractable (FPT) when parameterized by . This seminal result, due to Downey and Fellows, follows from the Robertson-Seymour theorem establishing that the minor relation forms a well-quasi-ordering on finite graphs, which enables dynamic programming over finitely many obstruction sets. The well-quasi-ordering implies that for any fixed , there are only finitely many minimal forbidden minors, facilitating an FPT algorithm despite the tower-like dependence of on . When parameterized by the treewidth of , -minor containment is also FPT, even with unrestricted, because the property can be expressed in monadic second-order (MSO) logic. Courcelle's theorem guarantees that any MSO-definable graph property is recognizable in FPT time via dynamic programming on a tree decomposition of . Some variants of minor testing exhibit hardness in parameterized complexity. For instance, the induced topological minor problem—determining if contains an induced subdivision of —is W[57]-hard parameterized by , even when restricted to line graphs of and . This hardness arises from reductions from multicolored clique problems, highlighting that not all minor-like relations inherit the FPT tractability of standard minors.[58]References
- Its proof, due to Neil Robertson and Paul Seymour, takes well over 500 pages. So we have to be modest: of the actual proof of the graph minor theorem this ...