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
关键词
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 条
[11]   AN OMEGA(N4/3) LOWER BOUND ON THE RANDOMIZED COMPLEXITY OF GRAPH PROPERTIES [J].
HAJNAL, P .
COMBINATORICA, 1991, 11 (02) :131-143
[12]   ON PACKING BIPARTITE GRAPHS [J].
HAJNAL, P ;
SZEGEDY, M .
COMBINATORICA, 1992, 12 (03) :295-301
[14]  
Komlos J, 1998, RANDOM STRUCT ALGOR, V12, P297, DOI 10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO
[15]  
2-Q
[16]  
KOMLOS J, 1997, COMBINATORICA, V17, P108
[17]   EDGE DISJOINT PLACEMENT OF GRAPHS [J].
SAUER, N ;
SPENCER, J .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (03) :295-302
[18]  
Szemeredi E, 1976, P C INT CNRS PAR, P399