In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that, in any infinite class of finite, undirected, unlabelled graphs, there are two such that one is a contraction of a subgraph of the other.

PropertyValue
dbpprop:abstract
  • In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that, in any infinite class of finite, undirected, unlabelled graphs, there are two such that one is a contraction of a subgraph of the other. Another way to state the theorem is that, for every family F of (unlabeled, finite) graphs, such that if a graph is in the family then all its minors also are, there is a finite class O of finite graphs such that a graph G is in F if and only if no member of O is a minor of G . The members of O are called the excluded minors (or forbidden minors, or minor-minimal obstructions) for the family F . The significance of the theorem is the finiteness of the set of excluded minors. The statement is a generalisation of a version of Kuratowski's theorem on planar graphs due to the German mathematician Klaus Wagner. Neil Robertson and Paul D. Seymour called it Wagner's conjecture (although Wagner said he never conjectured it) until they proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. A weaker result for trees is implied by Kruskal's tree theorem, which was proved in 1960.
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that, in any infinite class of finite, undirected, unlabelled graphs, there are two such that one is a contraction of a subgraph of the other.
rdfs:label
  • Robertson–Seymour theorem
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of