Geodesic
Star-Critical Ramsey Numbers for Cycles versus K4
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 381-390.

Voir la notice de l'article provenant de la source Library of Science

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⊔ 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 
@article{DMGT_2021_41_2_a2,
     author = {Jayawardene, Chula J. and Narv\'aez, David and Radziszowski, Stanis{\l}aw P.},
     title = {Star-Critical {Ramsey} {Numbers} for {Cycles} versus {K\protect\textsubscript{4}}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {381--390},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a2/}
}
TY  - JOUR
AU  - Jayawardene, Chula J.
AU  - Narváez, David
AU  - Radziszowski, Stanisław P.
TI  - Star-Critical Ramsey Numbers for Cycles versus K4
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 381
EP  - 390
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a2/
LA  - en
ID  - DMGT_2021_41_2_a2
ER  - 
%0 Journal Article
%A Jayawardene, Chula J.
%A Narváez, David
%A Radziszowski, Stanisław P.
%T Star-Critical Ramsey Numbers for Cycles versus K4
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 381-390
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a2/
%G en
%F DMGT_2021_41_2_a2
Jayawardene, Chula J.; Narváez, David; Radziszowski, Stanisław P. Star-Critical Ramsey Numbers for Cycles versus K4. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 381-390. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a2/

[1] J.A. Bondy and P. Erdős, Ramsey number for cycles in graphs, J. Combin. Theory Ser. B 14 (1973) 46–54. doi:10.1016/S0095-8956(73)80005-X

[2] B. Bollobás, C. Jayawardene, J. Yang, Y. Huang, C. Rousseau and K. Zhang, On a conjecture involving cycle-complete graph Ramsey numbers, Australas. J. Combin. 22 (2000) 63–71.

[3] S.A. Burr, P. Erdős, R.J. Faudree, R.J. Gould, M.S. Jacobson, C.C. Rousseau and R.H. Schelp, Goodness of trees for generalized books, Graphs Combin. 3 (1987) 1–6. doi:10.1007/BF01788524

[4] M. Hansson, Generalised Ramsey numbers for two sets of cycles, preprint, 2016. arXiv:1605.04301 [math.CO]

[5] S. Haghi, H.R. Maimani and A. Seify, Star-critical Ramsey number of Fn vs K4, Discrete Appl. Math. 217 (2017) 203–209. doi:10.1016/j.dam.2016.09.012

[6] J. Hook, The Classification of Critical Graphs and Star-Critical Ramsey Numbers, Ph.D. Thesis (Lehigh University, 2010).

[7] J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011) 328–334. doi:10.1016/j.dam.2010.11.007

[8] C.J. Jayawardene and C.C. Rousseau, The Ramsey number for a cycle of length five vs. a complete graph of order six, J.Graph Theory 35 (2000) 99–108. doi:10.1002/1097-0118(200010)35:299::AID-JGT4 3.0.CO;2-6

[9] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2013) 94–112. doi:10.1016/j.jsc.2013.09.003

[10] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin., DS1, (2017) #15.

[11] C.C. Rousseau and C.J. Jayawardene, The Ramsey number for a quadrilateral vs. a complete graph on six vertices, Congr. Numer. 123 (1997) 97–108.

[12] J. Yang, Y. Yiru and K. Zhang, The value of the Ramsey number R(Cn, K4) is 3(n − 1) + 1 (n ≥ 4), Australas. J. Combin. 20 (1999) 205–206.

[13] Y. Wu, Y. Sun and S.P. Radziszowski, Wheel and star-critical Ramsey numbers for quadrilaterals, Discrete Appl. Math. 185 (2015) 260–271. doi:10.1016/j.dam.2015.01.003