info prev up next book cdrom email home

Robertson-Seymour Theorem

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\geq 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$.


Fellows, M. R. ``The Robertson-Seymour Theorems: A Survey of Applications.'' Comtemp. Math. 89, 1-18, 1987.

© 1996-9 Eric W. Weisstein