GRAPH MINORS .4. TREE-WIDTH AND WELL-QUASI-ORDERING

被引：80

作者：

ROBERTSON, N ^{[1
]}

SEYMOUR, PD ^{[1
]}

机构：

[1] BELLCORE,MORRISTOWN,NJ 07960

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1990年 / 48卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0095-8956(90)90120-O

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. © 1990.

引用

页码：227 / 254

页数：28

共 13 条

[1]

ARCHDEACON D, 1980, THESIS OHIO STATE U

[2] 103 GRAPHS THAT ARE IRREDUCIBLE FOR THE PROJECTIVE PLANE [J].

GLOVER, HH ;

HUNEKE, JP ;

WANG, CS .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) :332-370

[3]

Higman G., 1952, P LOND MATH SOC, V3, P326, DOI 10.1112/plms/s3-2.1.326

[4]

JENKYNS TA, 1969, 2ND P ANN ARB GRAPH, P87

[5]

Kruskal J.B, 1960, T AM MATH SOC, V95, P210, DOI DOI 10.2307/1993287

[6]

Mader W., 1972, J COMB THEORY B, V12, P105

[7]

Nash-Williams C. St. J. A., 1963, P CAMBRIDGE PHILOS S, V59, P833

[8] GRAPH MINORS .5. EXCLUDING A PLANAR GRAPH [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :92-114

[9] GRAPH MINORS .8. A KURATOWSKI THEOREM FOR GENERAL SURFACES [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (02) :255-288

[10] GRAPH MINORS .3. PLANAR TREE-WIDTH [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 36 (01) :49-64

← 1 2 →