On the Bolloba's-Eldridge conjecture for bipartite graphs

被引：18

作者：

Csaba, B. ^{[1
]}

机构：

[1] Hungarian Acad Sci, Anal Stochast Res Grp, H-6720 Szeged, Hungary

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2007年 / 16卷 / 05期

关键词：

D O I：

10.1017/S0963548307008395

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let G be a simple graph on n vertices. A conjecture of Bollobas and Eldridge [5] asserts that if 6(G) >= kn-1/k=1 then G contains any n vertex graph H with Delta(H) = k. We prove a strengthened version of this conjecture for bipartite, bounded degree 11, for sufficiently large n. This is the first result on this conjecture for expander graphs of arbitrary (but bounded) degree. An important tool for the proof is a new version of the Blow-Up Lemma.

引用

页码：661 / 691

页数：31

共 18 条

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

AIGNER, M ;

BRANDT, S .

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

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

Alon, N ;

Fischer, E .

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

[3]

[Anonymous], 1993, COMBINATORICS P ERDO

[4]

Azuma K., 1967, Tohoku Mathematical J., Second Series, V19, P357, DOI [10.2748/tmj/1178243286, DOI 10.2748/TMJ/1178243286]

[5] PACKINGS OF GRAPHS AND APPLICATIONS TO COMPUTATIONAL COMPLEXITY [J].

BOLLOBAS, B ;

ELDRIDGE, SE .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (02) :105-124

[6]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[7]

Corradi K., 1963, Acta Math. Acad. Sci. Hungar, V14, P423

[8] Proof of a conjecture of Bollobas and Eldridge for graphs of maximum degree three [J].

Csaba, B ;

Shokoufandeh, A ;

Szemerédi, E .

COMBINATORICA, 2003, 23 (01) :35-72

[9]

CSABA B, 2003, BOLLOBAS ELDRIDGE CO

[10]

HAJNAL A, 1970, COMBIATORIAL THEORY, V2

← 1 2 →