TOPICS
Search

Robertson-Seymour Theorem


The Robertson-Seymour theorem, also called the graph minor theorem, is a generalization of the Kuratowski reduction theorem by Robertson and Seymour, which states that the collection of finite graphs is well-quasi-ordered by minor embeddability, from which it follows that Kuratowski's "forbidden minor" embedding obstruction generalizes to higher genus surfaces.

Formally, for a fixed integer g>=0, there is a finite list of graphs L(g) with the property that a graph C embeds on a surface of genus g iff it does not contain, as a minor, any of the graphs on the list L.


See also

Forbidden Minor, Kuratowski Reduction Theorem, Graph Minor

Explore with Wolfram|Alpha

References

Fellows, M. R. "The Robertson-Seymour Theorems: A Survey of Applications." Comtemp. Math. 89, 1-18, 1987.Roberson, N. and Seymour, P. D. "Graph Minors--A Survey." In Surveys in Combinatorics (Ed. I. Anderson). Cambridge, England: Cambridge University Press, pp. 153-171, 1985.

Referenced on Wolfram|Alpha

Robertson-Seymour Theorem

Cite this as:

Weisstein, Eric W. "Robertson-Seymour Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Robertson-SeymourTheorem.html

Subject classifications