Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three (Q1878591)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three |
scientific article; zbMATH DE number 2099003
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three |
scientific article; zbMATH DE number 2099003 |
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
0.9190171
0 references
0.8951932
0 references
0.8863432
0 references
0.8810874
0 references
0.8786658
0 references
0.87823105
0 references
0.8751923
0 references
0.87483144
0 references
