For any fixed graph ,
it is possible to test whether is a minor of a given graph 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
is called a topological minor of a graph if a graph expansion of
is isomorphic to a subgraph of . Every topological minor is also a minor,
but the converse is not necessarily true.
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, Germany:
Springer, pp. 3-15, 2006.Fellows, M. R. and Langston, M. A.
"Nonconstructive Tools for Proving Polynomial-Time Decidability." J.
ACM35, 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.; Seymour, P. D.;
and Thomas, R. "The Four-Colour Theorem." J. Combin. Th. Ser. B70,
2-44, 1997. https://doi.org/10.1006/jctb.1997.1750.Robertson,
N. and Seymour, P. D. "Graph Minors. XIII. The Disjoint Paths Problem."
J. Combin. Th., Ser. B63, 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.
of a graph 
is a graph for which a copy of 
can be obtained from 
via repeated edge deletion,
vertex deletion, and/or edge
contraction.
or the complete
bipartite graph 
as a minor. Tutte three-edge-coloring
conjecture asserts that every snark has the Petersen
graph as a minor.
,
it is possible to test whether 
is a minor of a given graph 
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).
is called a topological minor of a graph 
if a graph expansion of
is isomorphic to a subgraph of 
. Every topological minor is also a minor,
but the converse is not necessarily true.
