Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three (Q1878591)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three |
scientific article |
Statements
Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three (English)
0 references
7 September 2004
0 references
If \(H\) is a graph with maximal degree 3 on \(n\geq n_0\) vertices and \(G\) is an \(n\)-vertex graph with minimal degree at least \((3n-1)/4\) then \(G\) contains \(H\) as a subgraph. This is the first unsolved case of the Bollobás-Eldridge conjecture on packing of graphs. The involved proof heavily uses the regularity lemma.
0 references
extremal graph theory, packing
0 references
regularity lemma
0 references