DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


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: 2017-09-25, Revised: 2018-11-05, Accepted: 2018-11-05, https://doi.org/10.7151/dmgt.2190

Abstract:

Given three graphs $G$, $H$ and $K$ we write $K\rightarrow (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\rightarrow (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} \rightarrow (G, H)$, where $n$ is the Ramsey number $r(G,H)$. When $n \geq 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

PDF
Close