Ramsey numbers for triangles versus almost-complete graphs to the fond memory of Paul Erdos

Brendan D. McKay; Konrad Piwakowski; Stanisław P. Radziszowski

Ramsey numbers for triangles versus almost-complete graphs to the fond memory of Paul Erdos

Brendan D. McKay^*, Konrad Piwakowski, Stanisław P. Radziszowski

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We show that, in any coloring of the edges of K₃₈ with two colors, there exists a triangle in the first color or a monochromatic K ₁₀-e (K₁₀ with one edge removed) in the second color, and hence we obtain a bound on the corresponding Ramsey number, R(K ₃,K₁₀-e) ≤ 38. The new lower bound of 37 for this number is established by a coloring of K₃₆ avoiding triangles in the first color and K₁₀-e in the second color. This improves by one the best previously known lower and upper bounds. We also give the bounds for the next Ramsey number of this type, 42 ≤ R(K₃, K₁₁-e) ≤ 47.

Original language	English
Pages (from-to)	205-214
Number of pages	10
Journal	Ars Combinatoria
Volume	73
Publication status	Published - Oct 2004

Cite this

@article{b3825d0581cd4decba8fa33f31ca1a66,

title = "Ramsey numbers for triangles versus almost-complete graphs to the fond memory of Paul Erdos",

abstract = "We show that, in any coloring of the edges of K38 with two colors, there exists a triangle in the first color or a monochromatic K 10-e (K10 with one edge removed) in the second color, and hence we obtain a bound on the corresponding Ramsey number, R(K 3,K10-e) ≤ 38. The new lower bound of 37 for this number is established by a coloring of K36 avoiding triangles in the first color and K10-e in the second color. This improves by one the best previously known lower and upper bounds. We also give the bounds for the next Ramsey number of this type, 42 ≤ R(K3, K11-e) ≤ 47.",

author = "McKay, {Brendan D.} and Konrad Piwakowski and Radziszowski, {Stanis{\l}aw P.}",

year = "2004",

month = oct,

language = "English",

volume = "73",

pages = "205--214",

journal = "Ars Combinatoria",

issn = "0381-7032",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - Ramsey numbers for triangles versus almost-complete graphs to the fond memory of Paul Erdos

AU - McKay, Brendan D.

AU - Piwakowski, Konrad

AU - Radziszowski, Stanisław P.

PY - 2004/10

Y1 - 2004/10

N2 - We show that, in any coloring of the edges of K38 with two colors, there exists a triangle in the first color or a monochromatic K 10-e (K10 with one edge removed) in the second color, and hence we obtain a bound on the corresponding Ramsey number, R(K 3,K10-e) ≤ 38. The new lower bound of 37 for this number is established by a coloring of K36 avoiding triangles in the first color and K10-e in the second color. This improves by one the best previously known lower and upper bounds. We also give the bounds for the next Ramsey number of this type, 42 ≤ R(K3, K11-e) ≤ 47.

AB - We show that, in any coloring of the edges of K38 with two colors, there exists a triangle in the first color or a monochromatic K 10-e (K10 with one edge removed) in the second color, and hence we obtain a bound on the corresponding Ramsey number, R(K 3,K10-e) ≤ 38. The new lower bound of 37 for this number is established by a coloring of K36 avoiding triangles in the first color and K10-e in the second color. This improves by one the best previously known lower and upper bounds. We also give the bounds for the next Ramsey number of this type, 42 ≤ R(K3, K11-e) ≤ 47.

UR - http://www.scopus.com/inward/record.url?scp=26844527408&partnerID=8YFLogxK

M3 - Article

SN - 0381-7032

VL - 73

SP - 205

EP - 214

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -

Ramsey numbers for triangles versus almost-complete graphs to the fond memory of Paul Erdos

Abstract

Other files and links

Fingerprint

Cite this