Star-Critical Ramsey Numbers for Cycles Versus K4

Abstract

Given three graphs G, H and K we write K → (G, H), if in any red/blue coloring of the edges of K there exists a red copy of G or a blue copy of H. The Ramsey number r(G, H) is defined as the smallest natural number n such that Kn → (G, H) and the star-critical Ramsey number r∗(G, H)is defined as the smallest positive integer k such that Kn−1K1,k → (G, H), where n is the Ramsey number r(G, H). When n ≥ 3, we show that r∗(Cn, K4)=2n except for r∗(C3, K4)=8and r∗(C4,K4) = 9. We also characterize all Ramsey critical r(Cn,K4) graphs.

Keywords

• ramsey theory
• star-critical ramsey numbers
• 05c55
• 05d10
• 05c38