Graph minors. IV. Tree-width and well-quasi-ordering

Neil Robertson; P. D. Seymour

doi:10.1016/0095-8956(90)90120-O

Graph minors. IV. Tree-width and well-quasi-ordering

Neil Robertson, P. D. Seymour

Research output: Contribution to journal › Article › peer-review

107 Scopus citations

Abstract

K. Wagner conjectured that if G₁, G₂, ... is any countable sequence of finite graphs, then there exist i, j with j > i ≥ 1 such that G_i is isomorphic to a minor of G_j. Kruskal proved this when G₁, G₂, ... are all trees. We prove a strengthening of Kruskal's result-Wagner's conjecture is true for all sequences in which G₁ is planar. We hope to show in a future paper that Wagner's conjecture is true in general, and the results of this paper will be needed for that proof.

Original language	English (US)
Pages (from-to)	227-254
Number of pages	28
Journal	Journal of Combinatorial Theory, Series B
Volume	48
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(90)90120-O
State	Published - Apr 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(90)90120-O

Cite this

@article{d46d8b5a44404f31a549615c3b4ba40e,

title = "Graph minors. IV. Tree-width and well-quasi-ordering",

abstract = "K. Wagner conjectured that if G1, G2, ... is any countable sequence of finite graphs, then there exist i, j with j > i ≥ 1 such that Gi is isomorphic to a minor of Gj. Kruskal proved this when G1, G2, ... are all trees. We prove a strengthening of Kruskal's result-Wagner's conjecture is true for all sequences in which G1 is planar. We hope to show in a future paper that Wagner's conjecture is true in general, and the results of this paper will be needed for that proof.",

author = "Neil Robertson and Seymour, {P. D.}",

note = "Funding Information: *Research partially supported by NSF grant number MCS 8103440",

year = "1990",

month = apr,

doi = "10.1016/0095-8956(90)90120-O",

language = "English (US)",

volume = "48",

pages = "227--254",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Graph minors. IV. Tree-width and well-quasi-ordering

AU - Robertson, Neil

AU - Seymour, P. D.

N1 - Funding Information: *Research partially supported by NSF grant number MCS 8103440

PY - 1990/4

Y1 - 1990/4

N2 - K. Wagner conjectured that if G1, G2, ... is any countable sequence of finite graphs, then there exist i, j with j > i ≥ 1 such that Gi is isomorphic to a minor of Gj. Kruskal proved this when G1, G2, ... are all trees. We prove a strengthening of Kruskal's result-Wagner's conjecture is true for all sequences in which G1 is planar. We hope to show in a future paper that Wagner's conjecture is true in general, and the results of this paper will be needed for that proof.

AB - K. Wagner conjectured that if G1, G2, ... is any countable sequence of finite graphs, then there exist i, j with j > i ≥ 1 such that Gi is isomorphic to a minor of Gj. Kruskal proved this when G1, G2, ... are all trees. We prove a strengthening of Kruskal's result-Wagner's conjecture is true for all sequences in which G1 is planar. We hope to show in a future paper that Wagner's conjecture is true in general, and the results of this paper will be needed for that proof.

UR - http://www.scopus.com/inward/record.url?scp=3042806238&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3042806238&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(90)90120-O

DO - 10.1016/0095-8956(90)90120-O

M3 - Article

AN - SCOPUS:3042806238

SN - 0095-8956

VL - 48

SP - 227

EP - 254

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Graph minors. IV. Tree-width and well-quasi-ordering

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this