Fact-checked by Grok 2 weeks ago

Graph minor

In graph theory, a graph minor is a graph H that can be obtained from another graph G by deleting some vertices and edges and contracting some edges, where contraction merges two adjacent vertices into a single vertex whose incident edges are the union of the originals, possibly with multiples removed.^[1] This operation preserves the essential connectivity structure while allowing for simplification, making minors a key tool for analyzing graph properties under topological transformations.^[2] The minor relation, denoted H ≼ G if H is a minor of G, defines a partial order on the set of all finite undirected graphs, which is transitive and reflexive (every graph is a minor of itself).^[3] A family of graphs is minor-closed if it contains all minors of its members, and such families are central to the study of graph structure, as they capture hereditary properties invariant under deletions and contractions.^[1] The foundational graph minors theorem, proved by Neil Robertson and Paul Seymour over a series of 20 papers spanning 1983 to 2004, states that the set of finite graphs under the minor relation forms a well-quasi-order: in every infinite sequence of finite graphs, there exist indices i < j such that the i-th graph is a minor of the j-th.^[1] This result implies that every minor-closed family of graphs is characterized by a finite list of forbidden minors, resolving a long-standing conjecture and enabling the finite description of such families.^[3] Beyond its theoretical depth, graph minor theory has significant algorithmic implications, including polynomial-time (cubic) algorithms to test whether a given graph contains a fixed minor H, and broader applications in solving problems like the disjoint paths problem and computing treewidth for graphs excluding specific minors.^[1] It also underpins structural results, such as the grid theorem linking high treewidth to large grid minors, and influences conjectures like Hadwiger's on chromatic number and clique minors.^[3]

Core Concepts

Definitions

In graph theory, a graph H is a minor of a graph G if a graph isomorphic to H can be obtained from G 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 G along with all edges incident to it. Edge deletion removes a single edge while preserving its endpoints. Edge contraction merges two adjacent vertices u and v into a single vertex, whose incident edges are the union of those originally incident to u or v; any resulting self-loops or multiple edges are then deleted to maintain simplicity.^[4] The minor relation is denoted H \preceq G when H is a minor of G, forming a partial order on the set of finite graphs up to isomorphism.^[4] Equivalently, G \succsim H indicates the same relation. A model of the minor H in G consists of vertex-disjoint connected subgraphs of G, called branch sets, one for each vertex of H; for every edge in H between vertices x and y, there is an edge in G between the corresponding branch sets V_x and V_y. These branch sets capture the structure obtained after contractions, with edges in H realized by direct connections or paths within G.^[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 H is a minor of G and K is a minor of H, then K is a minor of G, since the sequence of edge deletions, vertex deletions, and edge contractions that yield H from G can be followed by those that yield K from H. The relation is also antisymmetric, meaning that if G has H as a minor and H has G as a minor, then G and H are isomorphic. A family of graphs is minor-closed if it contains all minors of its members; that is, whenever G belongs to the family and H is a minor of G, then H 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 H is a minor of G, then |V(H)| \leq |V(G)| and |E(H)| \leq |E(G)|, 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 P_n on n vertices is a connected graph consisting of a sequence of n-1 edges forming a chain without branches or cycles. Any shorter path P_m with m < n is a minor of P_n, 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 C_4, a 4-vertex cycle with edges forming a square, is a minor of the complete graph K_4 on 4 vertices, where every pair of vertices is connected. To obtain C_4 from K_4, delete the two diagonal edges that cross the square; the remaining four edges form exactly C_4 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 T, being an acyclic connected graph, can be obtained as a minor from a more complex graph G that contains T as a spanning subgraph with additional cycles by contracting edges within those cycles. For instance, if G has cycles attached to the branches of T, 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 G into T 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 K_3 (a triangle) as a minor from the larger complete graph K_4. Start with K_4, which has vertices a, b, c, d and all six possible edges. Select one edge, say between a and b, and contract it: merge a and b into a new vertex w, remove the self-loop at w, and replace any parallel edges with singles (though none arise here). The resulting graph now has vertices w, c, d with edges w-c, w-d, and c-d, forming exactly K_3. 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 G is disconnected with components of sizes at most k vertices, then G cannot have a connected minor with more than k 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 K_2s (each a single edge) have no connected minor larger than K_2, 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 K_5 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 K_5, 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 K_5 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: K_{3,3} and K_5. The utility graph, isomorphic to K_{3,3}, directly embeds K_{3,3} 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, K_5 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 K_5 and K_{3,3} as minors despite lacking a subdivision of K_5 (though containing one of K_{3,3}) due to its symmetry and degree constraints; for K_{3,3}, 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 k \times k-grid as a minor, where the toroidal grid wraps edges around the surface; large such grids (e.g., k \geq 5) are non-planar, as they violate Euler's formula with k^2 vertices and $2k^2 edges exceeding $3k^2 - 6, 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 K_5 nor the complete bipartite graph K_{3,3} 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 K_5 and K_{3,3}. For K_5, with 5 vertices and 10 edges, Euler's formula for planar graphs implies that a simple connected planar graph on v \geq 3 vertices satisfies e \leq 3v - 6, but here $10 > 3 \cdot 5 - 6 = 9, yielding a contradiction.^[12] For K_{3,3}, which is bipartite with 6 vertices and 9 edges, the corresponding bound for bipartite planar graphs is e \leq 2v - 4, but $9 > 2 \cdot 6 - 4 = 8; 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 K_5 or K_{3,3} 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 i < j such that the i-th graph is a minor of the j-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 H. 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 H 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 (O(n^3)) to determine whether a given n-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 K_t as a minor is (t-1)-colorable for any integer t \geq 1.^[16] Equivalently, the conjecture asserts that the Hadwiger number \eta(G), defined as the largest integer t such that K_t is a minor of the graph G, satisfies \eta(G) \geq \chi(G), where \chi(G) is the chromatic number of G. 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 K_5 minors are 4-colorable, a result later proved in 1976.^[16] Hadwiger himself verified the conjecture for t \leq 4, noting its equivalence to the four-color theorem for t=5 via Wagner's earlier work on planar graphs and K_5-minor-free graphs.^[18] For t=6, Robertson, Seymour, and Thomas established the result in 1993 by showing that every K_6-minor-free graph is 5-colorable, building on structural characterizations from graph minor theory.^[18] These cases confirm the conjecture for t \leq 6, but despite extensive searches, no counterexamples have been found for larger t, leaving it open for t \geq 7.^[16] Partial progress includes connections to the stronger but disproved Hajós conjecture from 1961, which claimed that graphs with chromatic number at least t contain a K_t 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 K_t minors exhibit bounded degeneracy, as every such graph has average degree at most O(t \sqrt{\log t}), implying they are O(t \sqrt{\log t})-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 \eta(G) relative to \chi(G).^[20] Recent improvements refine the degeneracy bound to O(t (\log \log t)^5)-colorability for K_t-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 H provides a decomposition that reveals the hierarchical organization of such graphs. Any H-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 K_5 and the complete bipartite graph K_{3,3} 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 K_4 and K_{2,3} 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 K_4 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 K_3 (a triangle) as a minor. Any contraction or deletion in a forest preserves acyclicity, making K_3 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 r \times r 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 r (with the current best bound \tilde{O}(r^9) as of 2025) contains an r \times r grid minor, linking minor exclusions to decomposability and algorithmic tractability.^[31]

Variants of Graph Minors

Topological Minors

A graph H is a topological minor of a graph G if G contains a subdivision of H as a subgraph, meaning that H can be obtained from a subgraph of G 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 H.^[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 H as a minor without containing a subdivision of H as a subgraph, particularly when H 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 K_5 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 K_5-minor does not necessarily impose such strong connectivity requirements.^[32] For complete graphs, the presence of K_n as a topological minor admits a precise characterization: a graph G contains K_n as a topological minor if and only if there exist n distinct vertices in G, each of degree at least n-1, 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 G is a graph H that can be obtained by first selecting an induced subgraph of G and then contracting a subset of its edges.^[33] Equivalently, H arises from G 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 \chi-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 (P_4, C_4)-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 G, also known as an immersion of a graph H in G, is defined by an injective mapping \phi: V(H) \to V(G) from the vertices of H to distinct vertices of G, together with a set of edge-disjoint paths in G such that for each edge uv in H, there is a path from \phi(u) to \phi(v) whose internal vertices are not in \phi(V(H)).^[38] This model ensures that the edges of H 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 H'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 G contains an immersion of the complete graph K_{\chi(G)}, 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 G with minimum degree at least $11t + 7 contains K_t 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 C k (for a constant C) contains a 2-immersion of the complete directed graph on k vertices, with paths of length at most 2.^[42]

Shallow Minors

In graph theory, a graph H is an r-shallow minor of a graph G (for some nonnegative integer r) if H can be obtained from a subgraph of G by contracting disjoint connected subgraphs, each of radius at most r, 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 r = 0) and arbitrary minors (as r 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 O(n^{1/2}) for graphs excluding a fixed r-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 \mathcal{G} has bounded expansion if the maximum average degree of its r-shallow minors is bounded by a function f_{\mathcal{G}}(r), 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 G is obtained via an odd H-expansion, where a subgraph is expanded from H 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 H-minors, where each cycle in the model H in G has a specified parity (even or odd length modulo 2).^[48] For instance, detecting an odd K_k-minor requires all corresponding cycles in G 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 k disjoint odd cycles or odd cliques as minors, with runtime O(m \alpha(m,n) n) for fixed k.^[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 H is an oriented minor of G if H arises from a subgraph of G by contracting directed edges, thereby preserving arc directions in the model.^[53] This ensures that paths and cycles in H correspond to directed paths in G, 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 K_{3,3} 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 G contains a fixed graph H 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 H remained open, with no general algorithm known, even allowing exponential time; only specific cases, such as testing for small complete graph minors like K_3 (triangle detection), could be handled efficiently using methods like matrix multiplication in O(n^\omega) time where \omega \approx 2.373. Early approaches for general H relied on brute-force enumeration of potential branch sets—disjoint connected subgraphs in G corresponding to vertices of H—followed by verification of inter-set connections via edge contractions and deletions, yielding algorithms exponential in both |V(H)| and n = |V(G)|, such as O(2^{|V(H)|} n^{O(|V(H)|)}) time via recursive subdivision checks. These methods were impractical beyond very small H 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 H. The general approach constructs such an algorithm using dynamic programming on a tree decomposition of G with treewidth bounded by a function f(|H|) 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 O(f(|H|) n^3) 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 f grows extremely rapidly with |H|, rendering it non-practical for all but tiny H. For small fixed H, simpler naive implementations achieve O(n^3) time by simulating contractions through iterative subgraph searches—enumerating candidate connected components for each vertex of H 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 H is planar, recognition algorithms achieve linear time O(n). Robertson and Seymour's Graph Minors V provides a seminal O(n) 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 H. More recent planarity testing algorithms, such as the Boyer–Myrvold framework, enable efficient detection of specific planar minors like K_5 or K_{3,3} (topological equivalents for planarity) by adding edges and checking for subdivisions in O(n) time using DFS-based certification and reduction rules, extending naturally to general fixed planar H 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 |H| is small (e.g., |V(H)| \leq 10), often running in seconds for sparse inputs but scaling poorly beyond. For larger sparse graphs and H 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 G contains a fixed graph H as a minor can be approached through parameterized complexity, where the parameter is typically the size of H, denoted |V(H)|, or the treewidth of G. Parameterization by |V(H)| treats H as the small input component, allowing algorithms whose running time is f(|V(H)|) \cdot n^{O(1)} for some function f and input size n = |V(G)| + |E(G)|. In contrast, parameterization by treewidth of G exploits structural sparsity in G, even when H is arbitrary and part of the input. The H-minor containment problem is fixed-parameter tractable (FPT) when parameterized by |V(H)|. 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 H, there are only finitely many minimal forbidden minors, facilitating an FPT algorithm despite the tower-like dependence of f on |V(H)|. When parameterized by the treewidth of G, H-minor containment is also FPT, even with H 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 f(\text{treewidth}(G)) \cdot n^{O(1)} via dynamic programming on a tree decomposition of G. Some variants of minor testing exhibit hardness in parameterized complexity. For instance, the induced topological minor problem—determining if G contains an induced subdivision of H—is W^[57]-hard parameterized by |V(H)|, even when restricted to line graphs of G and H. 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

[1]
[PDF] Graph Minors
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 ...
[2]
Graph Minor -- from Wolfram MathWorld
A graph H is a minor of a graph G if a copy of H can be obtained from G via repeated edge deletion and/or edge contraction.
[3]
[PDF] Graph Minor Theory
Mar 13, 2017 · 1.1 Minors. By contraction of an edge uv in a graph G we mean identification of u and v, i.e. replacement.
[4]
[PDF] Reinhard Diestel - Graph Theory
This fifth edition of the book is again a major overhaul, in the spirit of its first and third edition. I have rewritten Chapter 12 on graph minors to take ...
[5]
Graph minors. I. Excluding a forest - ScienceDirect
View PDF; Download full issue. Search ScienceDirect ... Graph minors. I. Excluding a forest. Author links open overlay panelNeil Robertson, P.D. Seymour.
[6]
[PDF] 12 Graph Minors - Jeff Erickson
A minor of a graph G is a graph obtained from G by contracting edges, deleting edges, and deleting isolated vertices; a proper minor of G is any minor other ...
[7]
[PDF] Section 10.5. Kuratowski's Theorem
Apr 6, 2023 · A minor which is isomorphic to K5 or K3,3 is a Kuratowski minor. A subdivision of K5 or K3,3 is a Kuratowski subdivision. Note 10.5. A.
[8]
[PDF] Math 228: Kuratowski's Theorem
A topological minor of a graph G is any graph H that can be transformed into G by a series of contractions, edge deletions, and/or removal of isolated vertices.
[9]
Sur le problème des courbes gauches en Topologie - EuDML
Kuratowski, Casimir. "Sur le problème des courbes gauches en Topologie." Fundamenta Mathematicae 15.1 (1930): 271-283. <http://eudml.org/doc/ ...
[10]
Toroidal grid minors and stretch in embedded graphs - ScienceDirect
We investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor.
[11]
Über eine Eigenschaft der ebenen Komplexe
Wagner, K. Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114, 570–590 (1937). https://doi.org/10.1007/BF01594196Missing: Klaus | Show results with:Klaus
[12]
[PDF] Planar Graphs and Wagner's and Kuratowski's Theorems
Aug 29, 2015 · A subdivision of K3,3. 3. Wagner's Theorem. In 1937, Klaus Wagner came up with another characterization of planar graphs that is, in fact ...
[13]
[PDF] The proof of Tutte's and Wagner's theorems; Hadwiger's conjecture
Oct 22, 2020 · We are now ready to finish the characterization. Theorem 6 (Wagner). A graph G is planar if and only if K5,K3,3 6 m G. Proof.
[14]
[PDF] Graph minors XX. Wagner's conjecture - Math (Princeton)
We prove Wagner's conjecture, that for every infinite set of finite graphs, one of its members is isomorphic to a minor of another. Page 3. 1 Introduction. A ...Missing: original | Show results with:original
[15]
None
### Summary of Graph Minors Project by Robertson and Seymour
[16]
[PDF] Hadwiger's conjecture - Math (Princeton)
Apr 16, 2015 · Proving that graphs with no K7-minor are 6-colourable is thus the first case of. Hadwiger's conjecture that is still open. Albar and Gonçalves[2] ...
[17]
A Relative of Hadwiger's Conjecture - SIAM.org
A hole in $G$ is an induced cycle of length at least four. Hadwiger's conjecture from 1943 states that for every graph $G$, $h(G)\ge \chi(G)$, where $\chi(G)$ ...
[18]
Hadwiger's conjecture forK 6-free graphs | Combinatorica
About this article. Cite this article. Robertson, N., Seymour, P. & Thomas, R. Hadwiger's conjecture forK 6-free graphs. Combinatorica 13, 279–361 (1993).
[19]
[PDF] ON THE CONJECTURE OF HAJÓS
Various relationships between the Hajós conjecture, the Four colour Theorem and the Hadwiger Conjecture are discussed in [11]. AMS (1980) subject ...
[20]
[2006.11798] Further progress towards Hadwiger's conjecture - arXiv
Jun 21, 2020 · In the 1980s, Kostochka and Thomason independently proved that every graph with no K_t minor has average degree O(t\sqrt{\log t}) and hence ...
[21]
Improved Bound for Hadwiger's Conjecture - ACM Digital Library
Feb 18, 2025 · Recently, Postle improved it to O ( t ( log log t ) 6 ) -colorable. In this paper, we show that every graph with no K t -minor is ...<|control11|><|separator|>
[22]
https://doi.org/10.1007/978-3-540-32439-3_17
[23]
[PDF] a survey - Math (Princeton)
Sep 19, 2023 · sharp in another sense. Let us say a class of graphs Fis minor-closed if for all G E ! F, every graph isomorphic to a minor of G is also in ! F.
[24]
[PDF] Graph Minors. XV. Giant Steps - CORE
GRAPH MINORS. XV. GIANT STEPS. Page 3. V(S), arrangement, T-local, bridge, H-path in G (called an ``H-pathing'' in [5], due to a typographical error). Let (G ...
[25]
[PDF] Minor-Closed Graph Classes with Bounded Layered Pathwidth - arXiv
Oct 19, 2018 · A minor-closed class has bounded layered treewidth if and only if some apex graph is not in the class. Theorem 3 generalises the above-mentioned ...
[26]
[PDF] Algorithmic Graph Minor Theory: Decomposition, Approximation ...
This section describes the Robertson-Seymour decom- position theorem characterizing the structure of H-minor- free graphs, which we make algorithmic in this ...
[27]
Bemerkungen zum Vierfarbenproblem. - EuDML
Wagner, K.. "Bemerkungen zum Vierfarbenproblem.." Jahresbericht der Deutschen Mathematiker-Vereinigung 46 (1936): 26-32. <http://eudml.org/doc/146109>.Missing: Klaus forbidden minors
[28]
https://doi.org/10.1016/0012-365X(79)90060-8
[29]
[PDF] Diestel: Graph Theory - PRIP
There are two areas of graph theory which I find both fascinat- ing and important, especially from the perspective of pure mathematics adopted here, but which ...<|control11|><|separator|>
[30]
[PDF] Induced Minor Models. I. Structural Properties and Algorithmic ...
A graph H is said to be an induced minor of a graph G if H can be obtained from G by a sequence of vertex deletions and edge contractions. Equivalently,.
[31]
Induced minors and well-quasi-ordering - ScienceDirect
A graph H is 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 ...
[32]
[PDF] Induced Minors and Region Intersection Graphs
Each Xu is called a branch set. A graph H is an induced minor of a graph G if H is isomorphic to a graph that can be obtained from an induced subgraph of G ...
[33]
[PDF] Contractions in perfect graphs - arXiv
Jan 23, 2024 · characterization of perfect graphs by forbidden induced minors ... Trivially perfect graphs are interval graphs, split and interval graphs are ...
[34]
Treewidth versus clique number. I. Graph classes with a forbidden ...
Jun 10, 2020 · Our results yield an infinite family of \chi-bounded induced-minor-closed ... bounded, leading to linear-time algorithms for k-coloring 1 ...
[35]
[PDF] Complete graph immersions and minimum degree.
Dec 3, 2015 · An immersion of a graph H in a graph G is a one-to-one mapping ϕ : V (H) → V (G) and a collection of edge-disjoint paths in G, one for each edge.
[36]
[2305.06204] Immersions of directed graphs in tournaments - arXiv
May 10, 2023 · If one insists in finding an immersion of a complete directed graph on k vertices then an extra condition on the tournament is necessary.Missing: K_n theory<|control11|><|separator|>
[37]
On a special case of Hadwiger's Conjecture - ResearchGate
Aug 9, 2025 · Hadwiger's conjecture for the immersion relation posits that every graph G contains an immersion of the complete graph K χ ( G ) K_{\chi(G)} .
[38]
[PDF] Graph Minors XXIII. Nash-Williams' immersion conjecture
We define a quasi-order of the class of all finite hypergraphs, and prove it is a well-quasi-order. This has two corollaries of interest:.
[39]
Immersions of Directed Graphs in Tournaments - Wiley Online Library
Nov 20, 2024 · We show that every tournament with minimum out-degree at least must contain a 2-immersion of a complete digraph on vertices.
[40]
[PDF] Cop-Width, Flip-Width and Strong Colouring Numbers
May 6, 2025 · Let G be a graph and r ≥ 0 be an integer. A graph H is an r-shallow minor of G if H can be obtained from a subgraph of G by contracting ...<|control11|><|separator|>
[41]
Shallow excluded minors and improved graph decompositions
First consider a graph that is a square of a bounded- degree planar graph. The theory of graph minors is of little use for such graphs, since they can have ...
[42]
Sparsity: Graphs, Structures, and Algorithms | SpringerLink
Available as PDF; Read on any device; Instant download; Own it forever. Buy eBook ... Jaroslav Nešetřil, Patrice Ossona de Mendez. Pages 3-5. A Few Problems.
[43]
Shallow Minors, Graph Products and Beyond Planar Graphs - arXiv
Nov 24, 2021 · In this paper, we extend this line of research by utilizing shallow minors to prove analogous product structure theorems for several beyond planar graph ...Missing: Gromov- Hausdorff
[44]
[PDF] Odd Minors I - arXiv
Apr 10, 2023 · Roughly speaking, the odd-minor relation is a restriction of the minor relation of graphs that preserves parities of cycles.
[45]
[PDF] The Graph Minor Algorithm with Parity Conditions - La Sapienza
The main algorithmic result of the Graph Minor Theory is a polynomial-time algorithm for testing the existence of a fixed minor [55] which, combined with the ...
[46]
[PDF] Regular matroid decomposition via signed graphs
A minor of G;ΣŮ is a signed graph that comes from G;ΣŮ by a series of the following operations: re- signing, deletion of an edge or isolated vertex, and ...<|separator|>
[47]
Is there a version of Robertson-Seymour's graph minor theorem ...
Jan 2, 2016 · Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges.Is there a version of Robertson-Seymour's graph minor theorem for ...Is there a polynomial-time algorithm to check if a signed graph ...More results from mathoverflow.net
[48]
[PDF] Homomorphisms of signed graphs: An update - HAL
Oct 17, 2020 · A signed graph has signed edges. A homomorphism preserves incidence, adjacency, and the signs of closed walks. This extends classical graph ...
[49]
Some minor-closed classes of signed graphs - ScienceDirect.com
Feb 28, 2013 · We define four minor-closed classes of signed graphs in terms of embeddability in the annulus, projective plane, torus, and Klein bottle.
[50]
Directed graph minor theorems - MathOverflow
Jun 28, 2020 · A directed graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges.
[51]
[1711.01806] Directed Graph Minors and Serial-Parallel Width - arXiv
Nov 6, 2017 · Abstract:Graph minors are a primary tool in understanding the structure of undirected graphs, with many conceptual and algorithmic ...Missing: oriented | Show results with:oriented
[52]
[PDF] A survey of Pfaffian orientations of graphs - Robin Thomas
A Pfaffian orientation of a graph has every even cycle with a perfect matching having an odd number of edges directed in either direction.
[53]
Can every maximal planar graph be obtained as a minor of a planar ...
Jul 2, 2019 · The question is whether every maximal planar graph G1 (with arbitrary even and/or odd vertex degrees) can be obtained in that way as a minor of ...
[54]
Undirected graphs - Graph Theory - SageMath Documentation
Compute the matching polynomial of the graph $G$. minor(). Return the vertices of a minor isomorphic to $H$ in the current graph. pathwidth(). Compute the ...
[55]
[PDF] arXiv:1202.4419v2 [cs.DM] 6 Mar 2014
Mar 6, 2014 · We prove in Section 5 that Induced Topological Minor is. W[1]-hard when parameterized by |V (H)|, even if G and H are line graphs. This means ...