The Ramsey numbers for disjoint unions of cycles (Q1910566)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The Ramsey numbers for disjoint unions of cycles
scientific article

    Statements

    The Ramsey numbers for disjoint unions of cycles (English)
    0 references
    0 references
    25 March 1996
    0 references
    Let \(G\) and \(H\) be graphs and define the Ramsey number \(r(G, H)\) to be the smallest positive integer \(n\) so that any two colorings of the edge set of the complete graph on \(n\) vertices results in a copy of \(G\) with all of its edges colored with the first color or in a copy of \(H\) with all of its edges colored with the second color. If \(G\) is any graph and \(k\) a positive integer, \(kG\) will denote the graph consisting of \(k\) vertext disjoint copies of \(G\). Finally, \(C_k\) will denote the circuit of length \(k\). The author proves several results of which the following is representative. Theorem 10. Let \(k\geq 5\) and \(1\leq m\leq n\). Then \(kn+ 3m- 1\leq r(nC_k, mC_5)\leq kn+ 3m+ (k- 4)\). In particular, setting \(k= 5\) gives the general Ramsey number for disjoint 5-cycles: \(5n+ 3m- 1\leq r(nC_5, mC_5)\leq 5n+ 3m+ 1\).
    0 references
    disjoint unions of cycles
    0 references
    Ramsey number
    0 references
    circuit
    0 references

    Identifiers