Graph structure theorem
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. and are surveys accessible to nonspecialists, describing the theorem and its consequences.
In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. and are surveys accessible to nonspecialists, describing the theorem and its consequences.
Refinements
Strengthened versions of the graph structure theorem are possible depending on the set of forbidden minors. For instance, when one of the graphs in is planar, then every -minor-free graph has a tree decomposition of bounded width; equivalently, it can be represented as a clique-sum of graphs of constant size. When one of the graphs in can be drawn in the plane with only a single crossing, then the -minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices. A different strengthening is also known when one of the graphs in is an apex graph.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1354296200 under CC BY-SA 4.0; modifications have been made.