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