GRAPH MINORS .8. A KURATOWSKI THEOREM FOR GENERAL SURFACES

被引：74

作者：

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)90121-F

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that for any infinite set of graphs of bounded genus, some member of the set is isomorphic to a minor of another. As a consequence, for any surface Σ there is a finite list of graphs, such that a general graph may be drawn in Σ if an only if it topologically contains none of the graphs in the list. © 1990.

引用

收藏

页码：255 / 288

页数：34

相关论文

共 11 条

[1] A KURATOWSKI THEOREM FOR NONORIENTABLE SURFACES [J].

ARCHDEACON, D ;

HUNEKE, P .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :173-231

[2]

ARCHDEACON D, 1980, THESIS OHIO STATE U

[3] 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

[4]

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

[5]

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

[6]

Kuratowski, 1930, FUND MATH, V15, P271

[7] GRAPH MINORS .4. TREE-WIDTH AND WELL-QUASI-ORDERING [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (02) :227-254

[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 .6. DISJOINT PATHS ACROSS A DISK [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :115-138

[10] GRAPH MINORS .7. DISJOINT PATHS ON A SURFACE [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 45 (02) :212-254