Embedding grids in surfaces

被引：21

作者：

Geelen, JF ^{[1
]}

Richter, RB

Salazar, G

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Univ Autonoma San Luis Potosi, Inst Invest Comun Opt, San Luis Potosi 78210, Mexico

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2004年 / 25卷 / 06期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/j.ejc.2003.07.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that if a very large grid is embedded in a surface, then a large subgrid is embedded in a disc in the surface. This readily implies that: (a) a minor-minimal graph that does not embed OF in a given surface has no very large grid; and (b) a minor-minimal k-representative embedding in the surface has no very large grid. Similar arguments show (c) that if G is minimal with respect to crossing number, then G has no very large grid. This work is a refinement of Thomassen (J. Combin. Theory Ser. B 70 (1997) 306). (C) 2004 Elsevier Ltd. All rights reserved.

引用

页码：785 / 792

页数：8

共 14 条

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

[12]

ROBERTSON N, 1990, ALGORITHMS COMBINATO, V9, P293

[13] A MENGER-LIKE PROPERTY OF TREE-WIDTH - THE FINITE CASE [J].

THOMAS, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :67-76

[14] A simpler proof of the excluded minor theorem for higher surfaces [J].

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 70 (02) :306-311

← 1 2 →