Article in press
Authors:
Stanisław P. Radziszowski
Department of Computer Science
Rochester Institute of Technology
email: spr@cs.rit.edu
Title:
Some upper bounds on Ramsey numbers involving $C_4$
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-12-04 , Revised: 2024-07-31 , Accepted: 2024-07-31 , Available online: 2024-09-06 , https://doi.org/10.7151/dmgt.2557
Abstract:
We obtain some new upper bounds on the Ramsey numbers of the form
$$
R(\underbrace{C_4,\ldots,C_4}_m,G_1,\ldots,G_n),
$$
where $m\ge 1$ and $G_1,\ldots,G_n$ are arbitrary graphs. We focus on the cases
of $G_i$'s being complete graph $K_k$, star $K_{1,k}$ or book $B_k$, where
$B_k=K_2+kK_1$. If $k\ge 2$, then our main upper bound theorem implies that
$$
R(C_4,B_k) \le R(C_4,K_{1,k})+\left\lceil\sqrt{R(C_4,K_{1,k})}\right\rceil+1.
$$
Our techniques are used to obtain new upper bounds in several
concrete cases, including: $R(C_4,K_{11})\leq 43$, $R(C_4,K_{12})\leq 51$,
$R(C_4,K_3,K_4)\leq 29$, $R(C_4,K_4,K_4)\leq 66$, $R(C_4,K_3,K_3,K_3)\leq 57$,
$R(C_4,C_4,K_3,K_4)\leq 75$, $R(C_4,C_4,K_4,K_4)\leq 177$, and
$R(C_4,B_{17})\leq 28$.
Keywords:
Ramsey numbers, cycles
References:
- D. Bevan, Personal communication to S. Radziszowski (2002), manuscript.
- F.R.K. Chung, On triangular and cyclic Ramsey numbers with $k$ colors, in: Graphs Combin., R. Bari and F. Harary (Ed(s)), Lect. Notes Math. 406, (Springer, Berlin, 1974) 236–241.
- J. Dybizbański and T. Dzido, On some Ramsey numbers for quadrilaterals, Electron. J. Combin. 18(1) (2011) #P154.
https://doi.org/10.37236/641 - A. Engel, Problem-Solving Strategies (Springer-Verlag New York, Inc, 1998).
- P. Erdős, A. Rényi and V.T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966) 215–235.
- G. Exoo and D.F. Reynolds, Ramsey numbers based on $C_5$-decompositions, Discrete Math. 71 (1988) 119–127.
https://doi.org/10.1016/0012-365X(88)90065-9 - R.J. Faudree, C.C. Rousseau and J. Sheehan, More from the Good Book, Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math. Congr. Numer. XXI (1978) 289–299.
- R.E. Greenwood and A.M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955) 1–7.
https://doi.org/10.4153/CJM-1955-001-4 - R.W. Irving, Generalised Ramsey numbers for small graphs, Discrete Math. 9 (1974) 251–264.
https://doi.org/10.1016/0012-365X(74)90008-9 - A. Lange, I. Livinsky and S.P. Radziszowski, Computation of the Ramsey numbers $R(C_4,K_9)$ and $R(C_4,K_{10})$, J. Combin. Math. Combin. Comput. 97 (2016) 139–154.
- B. Lidický and F. Pfender, Semidefinite programming and Ramsey numbers (2017, revised version 2020).
arXiv: 1704.03592 - T.D. Parsons, Ramsey graphs and block designs, I, Trans. Amer. Math. Soc. 209 (1975) 33–44.
https://doi.org/10.1090/S0002-9947-1975-0396317-X - S. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2024) DS1, revision #17.
- S. Van Overberghe, Algorithms for Computing Ramsey Numbers, MS Thesis in Mathematics, Ghent University, Belgium (2020).
https://github.com/Steven-VO/circulant-Ramsey - X. Xu and S.P. Radziszowski, $28\le R(C_4,C_4,C_3,C_3)\le 36$, Util. Math. 79 (2009) 253–257.
- X. Xu, Z. Shao and S.P. Radziszowski, Bounds on some Ramsey numbers involving quadrilateral, Ars Combin. 90 (2009) 337-344.
- X. Zhang, Y. Chen and T.C. Edwin Cheng, On three color Ramsey numbers for $R(C_4,C_4,K_{1,n})$, Discrete Math. 342 (2019) 285–291.
https://doi.org/10.1016/j.disc.2018.09.030
Close