| Version 7 |
Version 6 |
| \PMlinkescapeword{closed} |
\PMlinkescapeword{closed} |
| \PMlinkescapeword{class} |
\PMlinkescapeword{class} |
| \PMlinkescapeword{series} |
|
| If $(G_k)_{k\in\Bbb{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$. |
If $(G_k)_{k\in\Bbb{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 1996 as the culminating result of a series of 15 articles. It resolves Wagner's conjecture in the affirmative and leads to an important generalization of Kuratowski's theorem.
|
This theorem (proven by Robertson and Seymour) is often referred to as the deepest result in graph theory. 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 \emph{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 \emph{forbidden minors} for the class $\cal{G}$. |
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 \emph{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 \emph{forbidden minors} for the class $\cal{G}$. |
| \subsection{References} |
|
| \begin{itemize} |
|
| \item N. Robertson and P.D. Seymour. Graph Minors XV: giant steps. {\em Journal of Combinatorial Theory B} 68:112-148, 1996 |
|
| \end{itemize} |
|
