Robertson-Seymour Theorem
المؤلف:
Fellows, M. R
المصدر:
"The Robertson-Seymour Theorems: A Survey of Applications." Comtemp. Math. 89
الجزء والصفحة:
1-18
19-3-2022
2111
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 
, there is a finite list of graphs 
with the property that a graph 
embeds on a surface of genus 
iff it does not contain, as a minor, any of the graphs on the list 
.
REFERENCES
Fellows, M. R. "The Robertson-Seymour Theorems: A Survey of Applications." Comtemp. Math. 89, 1-18, 1987.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
