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
    0 references
    0 references
    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

    Identifiers