|
|
|
Viewing Version
10
of
'graph minor theorem'
|
[ view 'graph minor theorem'
|
back to history
]
| Title of object: |
graph minor theorem |
| Canonical Name: |
GraphMinorTheorem |
| Type: |
Theorem |
| Created on: |
2003-11-23 20:03:38 |
| Modified on: |
2004-01-20 10:24:11 |
| Classification: |
msc:05C99 |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
\PMlinkescapeword{closed}
\PMlinkescapeword{class}
\PMlinkescapeword{series}
\PMlinkescapeword{theory}
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.
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 XX: Wagner's conjecture. Preprint 1988, to appear in {\em Journal of Combinatorial Theory B}
\end{itemize} |
|
|
|
|
|
