An upper bound for the Ramsey numbers \(r(K_ 3,G)\)
type: Item
instance of: scholarly article
title: An upper bound for the Ramsey numbers \(r(K_ 3,G)\)
zbMATH Open document ID: 0795.05095
DOI: 10.1016/0012-365X(94)90158-9
author: Wayne Goddard
author: Daniel J. Kleitman
published in: Discrete Mathematics
publication date: 1994-09-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 562661
zbMATH Keywords: upper bound
zbMATH Keywords: Ramsey number
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: Q4120601
cites work: A Ramsey problem of Harary on graphs with prescribed size
cites work: An upper bound on the ramsey number R(K3, G) depending only on the size of the graph G
full work available at URL: 0012-365x(94)90158-9
OpenAlex ID: W2072863190
description: scientific article; zbMATH DE number 562661