Graph Minors. XX. Wagner's Conjecture

Robertson, N., & Seymour, P. D. (2004). Graph Minors. XX. Wagner's Conjecture. Journal of Combinatorial Theory, Series B, 92(2), 325-357.

Type

Journal article

Intellectual base

Primary research

Year

2004

DOI

10.1016/j.jctb.2004.08.001

Link

https://doi.org/10.1016/j.jctb.2004.08.001

Cited from

mathematics

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Embeddability
  • Forbidden-substructure characterisations decide embeddability by the presence or absence of a banned configuration: Kuratowski's theorem (planarity if and only if no \(K_5\) or \(K_{3,3}\) minor) is the canonical example, and Robertson–Seymour graph-minor theory extends the form to a vast class.

Domain-specific

• Partial k-tree
  • Consequently, for each fixed k, the class is minor-closed and has a finite forbidden-minor characterization, although the obstruction set becomes complicated as k increases

    This sourceRobertson and Seymour's proof of Wagner's conjecture is what makes the forbidden-minor set finite; the minor-closure of the class and the growth in complexity of the obstruction sets are separate points not established here.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:60b161ff3eed · see in the full table