Graph minors. IV: Tree-width and well-quasi-ordering (Q2639869)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4185635
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Graph minors. IV: Tree-width and well-quasi-ordering |
scientific article; zbMATH DE number 4185635 |
Statements
Graph minors. IV: Tree-width and well-quasi-ordering (English)
0 references
1990
0 references
[Part III, cf. ibid. 36, 49-64 (1984; Zbl 0548.05025.] The famous conjecture of K. Wagner says that if \(G_ 1,G_ 2,..\). is any countably infinite sequence of finite graphs, then there exist \(i,j,j>i\geq 1\) such that \(G_ i\) is isomorphic to a minor of \(G_ j\). By a result of Kruskal, this is true if all the \(G_ i's\) are trees. The authors extend Kruskal's theorem to all sequences in which the first member \(G_ 1\) is planar. This is one of the steps towards establishing the truth of Wagner's conjecture in general.
0 references
graph minor
0 references
tree-width
0 references
Wagner's conjecture
0 references
0.890502393245697
0 references
0.887920618057251
0 references
0.8771257400512695
0 references
0.87431401014328
0 references
