# MPI-I-2003-1-009

## On the Bollob\'as -- Eldridge conjecture for bipartite graphs

### Csaba, Bela

**MPI-I-2003-1-009**. March** **2003, 29 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Let $G$ be a simple graph on $n$ vertices. A conjecture of

Bollob\'as and Eldridge~\cite{be78} asserts that if $\delta (G)\ge {kn-1 \over

k+1}$

then $G$ contains any $n$ vertex graph $H$ with $\Delta(H) = k$.

We strengthen this conjecture: we prove that if $H$ is bipartite,

$3 \le \Delta(H)$ is bounded and $n$ is sufficiently large , then there exists

$\beta >0$ such that if $\delta (G)\ge {\Delta \over {\Delta +1}}(1-\beta)n$,

then

$H \subset G$.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 340 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-009

**BibTeX**
`@TECHREPORT{``Csaba2003``,`

` AUTHOR = {Csaba, Bela},`

` TITLE = {On the Bollob\'as -- Eldridge conjecture for bipartite graphs},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-2003-1-009},`

` MONTH = {March},`

` YEAR = {2003},`

` ISSN = {0946-011X},`

`}`