An upper bound for the Ramsey numbers \(r(K_ 3,G)\) (Q1322269)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An upper bound for the Ramsey numbers \(r(K_ 3,G)\) |
scientific article |
Statements
An upper bound for the Ramsey numbers \(r(K_ 3,G)\) (English)
0 references
11 September 1994
0 references
Given graphs \(H\) and \(G\), the Ramsey number \(r(H,G)\) is defined to be the smallest integer \(n\) so that, whenever the edges of the complete graph on \(n\) vertices \(K_ n\) is edge 2-colored, then either there is a copy of \(H\) in \(K_ n\) with all of its edges colored with the first color or a copy of \(G\) with all of its edges colored with the second color. This paper is devoted to proving the following result: For any graph \(G\) with \(q\) edges and without isolated vertices, \(r(K_ 3,G) \leq 2q + 1\). This result may be restated as follows: Any graph on \(2q+1\) vertices with independence number at most 2 contains every (isolated-free) graph on \(q\) edges.
0 references
upper bound
0 references
Ramsey number
0 references