On graphs with small Ramsey numbers. II. (Q558242)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On graphs with small Ramsey numbers. II.
scientific article

    Statements

    On graphs with small Ramsey numbers. II. (English)
    0 references
    0 references
    0 references
    5 July 2005
    0 references
    [For Part I see \textit{A. V. Kostochka} and \textit{V. Rödl}, J. Graph. Theory 37, 198--204 (2001; Zbl 0994.05094).] A graph \(G\) is \(d\)-degenerate if every subgraph of \(G\) has a vertex of degree at most \(d\). Burr and Erdős conjectured that the Ramsey number of a \(d\)-degenerate graph is linear, i.e., \(R(G,G)\leq c | V(G)| \), for some appropriate constant \(c=c(d)\). The authors prove the following statement in this spirit. If \(G_1\) and \(G_2\) are \(d\)-degenerate, then \(R(G_1,G_2)\leq cn\Delta (G_1)\), where \(c=c(d)\) and \(\Delta\) is the maximum degree of \(G_1\). An immediate corollary is that the Ramsey number of a \(d\)-degenerate graph is quadratic at most.
    0 references
    \(d\)-degenerate graphs
    0 references
    Burr-Erdős conjecture
    0 references

    Identifiers