graph minor theorem

If $(G_{k})_{k\\in\\mathbb{N}}$ is an infinite sequence of finite graphs, then there exist two numbers $m<n$ such that $G_{m}$ is isomorphic to a minor of $G_{n}$ .

This theorem is often referred to as the deepest result in graph theory. It was proven by Robertson and Seymour in 1988 as the culminating result of a long series of articles, and the proof was recently published in the Journal of Combinatorial Theory series B. It resolves Wagner’s conjecture in the affirmative and leads to an important generalization of Kuratowski’s theorem.

Specifically, to every set $\\cal{G}$ of finite graphs which is closed under taking minors (meaning if $G\\in\\cal{G}$ and $H$ is isomorphic to a minor of $G$ , then $H\\in\\cal{G}$ ) there exist finitely many graphs $G_{1},\\ldots,G_{n}$ such that $\\cal{G}$ consists precisely of those finite graphs that do not have a minor isomorphic to one of the $G_{i}$ . The graphs $G_{1},\\ldots,G_{n}$ are often referred to as the forbidden minors for the class $\\cal{G}$ .

0.1 References

•
Neil Robertson and P.D. Seymour. Graph Minors XX: Wagner’s conjecture. Journal of Combinatorial Theory B, Volume 92, Issue 2, November 2004, Pages 325-357. \\urlhttp://dx.doi.org/10.1016/j.jctb.2004.08.001

单词	GraphMinorTheorem
释义	graph minor theorem If $(G_{k})_{k\\in\\mathbb{N}}$ is an infinite sequence of finite graphs, then there exist two numbers $m<n$ such that $G_{m}$ is isomorphic to a minor of $G_{n}$ . This theorem is often referred to as the deepest result in graph theory. It was proven by Robertson and Seymour in 1988 as the culminating result of a long series of articles, and the proof was recently published in the Journal of Combinatorial Theory series B. It resolves Wagner’s conjecture in the affirmative and leads to an important generalization of Kuratowski’s theorem. Specifically, to every set $\\cal{G}$ of finite graphs which is closed under taking minors (meaning if $G\\in\\cal{G}$ and $H$ is isomorphic to a minor of $G$ , then $H\\in\\cal{G}$ ) there exist finitely many graphs $G_{1},\\ldots,G_{n}$ such that $\\cal{G}$ consists precisely of those finite graphs that do not have a minor isomorphic to one of the $G_{i}$ . The graphs $G_{1},\\ldots,G_{n}$ are often referred to as the forbidden minors for the class $\\cal{G}$ . 0.1 References • Neil Robertson and P.D. Seymour. Graph Minors XX: Wagner’s conjecture. Journal of Combinatorial Theory B, Volume 92, Issue 2, November 2004, Pages 325-357. \\urlhttp://dx.doi.org/10.1016/j.jctb.2004.08.001
随便看	alternative proof of the fundamental theorem of calculus AlternativeProofThatAFiniteIntegralDomainIsAField alternative proof that a finite integral domain is a field AlternativeProofThatsqrt2IsIrrational alternative proof that sqrt(2) is irrational AlternativeTreatmentOfConcatenation alternative treatment of concatenation AmalgamationProperty amalgamation property AmbiguousGrammar ambiguous grammar AmdahlsLaw Amdahl’s Law AmenableGroup amenable group AmenableNumber amenable number AmericanMathematicalSociety American Mathematical Society AmicableNumbers amicable numbers Ampheck ampheck AmphicheiralKnot amphicheiral knot