Authors: C.J. Jayawardene, D. Narváez, S.P. Radziszowski Title: Star-critical Ramsey numbers for cycles versus K_{4} Source: Discussiones Mathematicae Graph Theory Received 25.09.2017, Revised 05.11.2018, Accepted 05.11.2018, doi: 10.7151/dmgt.2190 | |
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 K_{n}→ (G,H) and the star-critical Ramsey number r_{*}(G, H) is defined as the smallest positive integer k such that K_{n-1} \sqcup K_{1,k} → (G, H), where n is the Ramsey number r(G,H). When n ≥ 3, we show that r_{*}(C_{n},K_{4})=2n except for r_{*}(C_{3},K_{4})=8 and r_{*}(C_{4},K_{4})=9. We also characterize all Ramsey critical r(C_{n},K_{4}) graphs. | |
Keywords: Ramsey theory, star-critical Ramsey numbers | |
Links: |