TOPICS
Search

Graph Minor


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.

The Kuratowski reduction theorem states that any nonplanar graph has the complete graph K_5 or the complete bipartite graph K_(3,3) as a minor. In addition, any snark has the Petersen graph as a minor, as conjectured by Tutte (1967; West 2000, p. 304) and proved by Robertson et al.

The determination of graph minors is an NP-hard problem for which no good algorithms are known, although brute-force methods such as those due to Robertson, Sanders, and Thomas exist.

Every graph minor is a topological minor, but the converse does not necessarily hold.

For any fixed graph H, it is possible to test whether H is a minor of an given graph G in polynomial time, so if a forbidden minor characterization is available, then any graph property which is preserved by deletions and contractions may be recognized in polynomial time (Fellows and Langston 1988, Robertson and Seymour 1995).

As of 2022, the plane and projective plane are the only surfaces for which a complete list of forbidden minors is known for graph embedding (Mohar and Škoda 2020).

A graph H is called a topological minor of a graph G if a graph expansion of H is isomorphic to a subgraph of G. Every topological minor is also a minor, but the converse is not necessarily true.


See also

Edge Contraction, Forbidden Minor, Kuratowski Reduction Theorem, Projective Plane Crossing Number, Robertson-Seymour Theorem, Topological Minor

This entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

Demaine, E. D.; Hajiaghayi, M.; and Kawarabayashi, K.-I. "Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring." In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, PA, October 23-25, 2005. pp. 637-646.Demaine, E. D.; Hajiaghayi, M.; and Kawarabayashi, K.-I. "Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction." In Algorithms and Computation. Proceedings of the 17th International Symposium (ISAAC 2006) held in Kolkata, December 18-20, 2006 (Ed. T. Asano). Berlin: Springer, pp. 3-15, 2006.Fellows, M. R. and Langston, M. A. "Nonconstructive Tools for Proving Polynomial-Time Decidability." J. ACM 35, 727-739, 1988.Mohar, B. and Škoda, P. "Excluded Minors for the Klein Bottle I. Low Connectivity Case." 1 Feb 2020. https://arxiv.org/abs/2002.00258.Robertson, N.; Sanders, D. P.; Seymour, P. D.; and Thomas, R. "A New Proof of the Four Colour Theorem." Electron. Res. Announc. Amer. Math. Soc. 2, 17-25, 1996.Robertson, N.; Sanders, D. P.; and Thomas, R. "The Four-Color Theorem." http://www.math.gatech.edu/~thomas/FC/fourcolor.html.Robertson, N. and Seymour, P. D. "Graph Minors. XIII. The Disjoint Paths Problem." J. Combin. Th., Ser. B 63, 65-110, 1995.Tutte, W. T. "A geometrical Version of the Four Color Problem." In Combinatorial Math. and Its Applications (Ed. R. C. Bose and T. A. Dowling). Chapel Hill, NC: University of North Carolina Press, 1967.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Graph Minor

Cite this as:

Pegg, Ed Jr. "Graph Minor." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/GraphMinor.html

Subject classifications