Proof of the bandwidth conjecture of Bollobas and Komlos

被引：55

作者：

Boettcher, Julia ^{[1
]}

Schacht, Mathias ^{[2
]}

Taraz, Anusch ^{[1
]}

机构：

[1] Tech Univ Munich, Zentrum Math, D-85747 Garching, Germany

[2] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

来源：

MATHEMATISCHE ANNALEN | 2009年 / 343卷 / 01期

关键词：

BLOW-UP LEMMA; DENSE GRAPHS; H-FACTORS; SUBGRAPHS; 2-FACTORS;

D O I：

10.1007/s00208-008-0268-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we prove the following conjecture by Bollobas and Komlos: For every gamma > 0 and integers r >= 1 and Delta, there exists beta > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r - 1)/r +gamma)n and H is an r-chromatic graph with n vertices, bandwidth at most beta n and maximum degree at most Delta, then G contains a copy of H.

引用

页码：175 / 205

页数：31

共 34 条

[1]

Abbasi S, 2000, GRAPH COMBINATOR, V16, P129

[2]

ABBASI S, EMBEDDING LOW UNPUB

[3] EMBEDDING ARBITRARY GRAPHS OF MAXIMUM DEGREE 2 [J].

AIGNER, M ;

BRANDT, S .

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1993, 48 :39-51

[4] 2-factors in dense graphs [J].

Alon, N ;

Fischer, E .

DISCRETE MATHEMATICS, 1996, 152 (1-3) :13-23

[5] ALMOST H-FACTORS IN DENSE GRAPHS [J].

ALON, N ;

YUSTER, R .

GRAPHS AND COMBINATORICS, 1992, 8 (02) :95-102

[6] H-factors in dense graphs [J].

Alon, N ;

Yuster, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 66 (02) :269-282

[7]

[Anonymous], J COMBIN THEORY B

[8] Spanning 3-colourable subgraphs of small bandwidth in dense graphs [J].

Boettcher, Julia ;

Schacht, Mathias ;

Taraz, Anusch .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (04) :752-777

[9]

BOTTCHER J, 2008, ELECT NOTES IN PRESS

[10]

Chung F.R.K., 1988, Sel. Top. Graph Theory, V3, P151

← 1 2 3 4 →