On induced Ramsey numbers for graphs with bounded maximum degree (Q1924131)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On induced Ramsey numbers for graphs with bounded maximum degree
scientific article

    Statements

    On induced Ramsey numbers for graphs with bounded maximum degree (English)
    0 references
    0 references
    0 references
    26 January 1997
    0 references
    The induced Ramsey number \(r_{\text{ind}}(H)\) for a graph \(H\) is defined as the minimum number of vertices in a graph \(G\) which has the property that every 2-edge colouring of \(G\) yields an induced monochromatic copy of \(H\). It is shown that for every \(d\geq 1\) there exists an absolute constant \(c_d\) such that \(r_{\text{ind}}(H_{n, d})\leq n^{c_d}\) for every graph \(H_{n, d}\) with \(n\) vertices and the minimum degree at most \(d\). This confirms a conjecture suggested by W. T. Trotter.
    0 references
    Ramsey number
    0 references

    Identifiers