Article in press
Authors:
Yang Sun
Hebei Normal University, School of Mathematical Sciences, Shijiazhuang, PR China
email: ysun.edu@outlook.com
Yanbo Zhang
Hebei Normal University, School of Mathematical Sciences, Shijiazhuang, PR China
email: ybzhang@hebtu.edu.cn
Title:
Star-critical Ramsey numbers of cycles revisited
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-04-19 , Revised: 2025-07-30 , Accepted: 2025-07-31 , Available online: 2025-08-29 , https://doi.org/10.7151/dmgt.2599
Abstract:
For integers $n \ge m \ge 3$, let $r_*(C_n, C_m)$ denote the star-critical
Ramsey number for a cycle of length $n$ versus a cycle of length $m$. The exact
value of $r_*(C_n, C_m)$ was determined for $m=4$ by Wu, Sun, and Radziszowski
(Wheel and star-critical Ramsey numbers for quadrilateral, Discrete Appl.
Math. 186 (2015) 260–271). Subsequently, Zhang, Broersma, and Chen
(On star-critical and upper size Ramsey numbers, Discrete Appl. Math.
202 (2016) 174–180) established
the exact value for all odd integers $m \ge 3$. However, the case of even
$m \ge 6$ has remained open. In this paper, we determine the exact value of
$r_*(C_n, C_m)$ for all even integers $m \ge 6$ and $n \ge \max\{3m/2+1, m+6\}$,
showing that
$$
r_*(C_n, C_m) = \frac{m}{2} + 3.
$$
Keywords:
Ramsey number, star-critical Ramsey number, cycle
References:
- J.A. Bondy and P. Erdős, Ramsey numbers for cycles in graphs, J. Combin. Theory Ser. B 14 (1973) 46–54.
https://doi.org/10.1016/S0095-8956(73)80005-X - J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135.
https://doi.org/10.1016/0012-365X(76)90078-9 - S. Brandt, A sufficient condition for all short cycles, Discrete Appl. Math. 79 (1997) 63–66.
https://doi.org/10.1016/S0166-218X(97)00032-2 - M.R. Budden, Star-Critical Ramsey Numbers for Graphs, Springer Briefs Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-29981-0 - G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. s3-2 (1952) 69–81.
https://doi.org/10.1112/plms/s3-2.1.69 - P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356.
https://doi.org/10.1007/BF02024498 - P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145–161.
https://doi.org/10.1007/BF02018930 - P. Erdős and R.J. Faudree, Size Ramsey functions, in: Sets, Graphs and Numbers, G. Halász, L. Lovász, D. Miklós and T. Szőny (Ed(s)), Colloq. Math. Soc. János. Bolyai 60, (North-Holland, Amsterdam, 1992) 219–238.
- R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313–329.
https://doi.org/10.1016/0012-365X(74)90151-4 - J. Hook, The Classification of Critical Graphs and Star-Critical Ramsey Numbers, Ph.D. Thesis (Lehigh University, 2010).
- J. Hook, Recent developments of star-critical Ramsey numbers, in: Combinatorics, Graph Theory and Computing: SEICCGTC 2021, F. Hoffman, S. Holliday, Z. Rosen and F. Shahrokki (Ed(s)), Springer Proc. Math. Stat. 448, (Springer, Cham, 2024) 245–254.
https://doi.org/10.1007/978-3-031-52969-6_22 - B. Jackson, Cycles in bipartite graphs, J. Combin. Theory Ser. B 30 (1981) 332–342.
https://doi.org/10.1016/0095-8956(81)90050-2 - S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2024) DS1.17.
https://doi.org/10.37236/21 - V. Rosta, On a Ramsey type problem of J.A. Bondy and P. Erdős, I, J. Combin. Theory Ser. B 15 (1973) 94–104.
https://doi.org/10.1016/0095-8956(73)90035-X - V. Rosta, On a Ramsey type problem of J.A. Bondy and P. Erdős, II, J. Combin. Theory Ser. B 15 (1973) 105–120.
https://doi.org/10.1016/0095-8956(73)90036-1 - Y. Wu, Y. Sun and S.P. Radziszowski, Wheel and star-critical Ramsey numbers for quadrilateral, Discrete Appl. Math. 186 (2015) 260–271.
https://doi.org/10.1016/j.dam.2015.01.003 - Y. Zhang, H. Broersma and Y. Chen, On star-critical and upper size Ramsey numbers, Discrete Appl. Math. 202 (2016) 174–180.
https://doi.org/10.1016/j.dam.2015.08.020
Close