Article in press
Authors:
Title:
Multicolor Ramsey numbers and star-critical Ramsey numbers involving fans
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-04-19 , Revised: 2024-01-09 , Accepted: 2024-01-10 , Available online: 2024-02-09 , https://doi.org/10.7151/dmgt.2539
Abstract:
For graphs $G$ and $H$,
the multicolor Ramsey number $r_{k+1}(G;H)$ is defined as the minimum integer
$N$ such that any edge-coloring of $K_N$ by $k+1$ colors contains either a
monochromatic $G$ in the first $k$ colors or a monochromatic $H$ in the last
color. We shall write two color Ramsey numbers as $r(G,H)$. For graphs $F$, $G$
and $H$, let $F\to (G,H)$ signify that any red/blue edge coloring of $F$
contains either a red $G$ or a blue $H$. Define the star-critical Ramsey number
$r^*(G,H)$ as $\max\{s\;|\;K_r\setminus K_{1,s}\to (G,H)\}$ where $r=R(G,H)$.
A fan $F_n$ is a graph that consists of $n$ copies of $K_3$ sharing a common
vertex, and a book $B^{(p)}_n$ is a graph that consists of $n$ copies of
$K_{p+1}$ sharing a common $K_p$. In this note, we shall show the upper bounds
for $r_{k+1}(K_{t,s};F_{n})$, $r_{k+1}(K_{2,s};F_{n})$, $r_{k+1}(C_{2t};F_{n})$,
some of which are sharp up to the sub-linear term asymptotically.
We also obtain the value of $r^*(F_m,B^{(p)}_n)$ as $n\to\infty$.
Keywords:
multicolor Ramsey number, star-critical Ramsey number, fan, book
References:
- B. Bollobás, Modern Graph Theory, Grad. Texts in Math. 184 (Springer, New York, 1998).
https://doi.org/10.1007/978-1-4612-0619-4 - J.A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combin. Theory Ser. B 16 (1974) 97–105.
https://doi.org/10.1016/0095-8956(74)90052-5 - S.A. Burr, Ramsey numbers involving graphs with long suspended paths, J. Lond. Math. Soc. 24 (1981) 405–413.
https://doi.org/10.1112/jlms/s2-24.3.405 - G. Chen, X. Yu and Y. Zhao, Improved bounds on the Ramsey number of fans, European J. Combin. 96 (2021) 103347.
https://doi.org/10.1016/j.ejc.2021.103347 - D. Conlon, The Ramsey number of books, Adv. Comb. 3 (2019).
https://doi.org/10.19086/aic.10808 - V. Dvořák and H. Metrebian, A new upper bound for the Ramsey number of fans, European J. Combin. 110 (2023) 103680.
https://doi.org/10.1016/j.ejc.2022.103680 - P. Erdős, On the number of complete subgraphs contained in certain graphs, Publ. Math. Inst. Hung. Acad. Sci. VII Ser. A3 (1962) 459–464.
- P. Erdős, Some recent results on extremal problems in graph theory, in: Theory of Graphs, Interna. Symposium in Rome, Gordon and Breach, (New York 1966) 117–130.
- P. Erdős, On some new inequalities concerning extremal properties of graphs, in: Theory of Graphs, Proceedings of the Colloquium in Tihany, Hungary, P. Erdős, G. Katona (Ed(s)), (Academic Press, New York 1968) 77–81.
- P. Erdős, Z. Füredi, R.J. Gould and D.S. Gunderson, Extremal graphs for intersecting triangles, J. Combin. Theory Ser. B 64 (1995) 89–100.
https://doi.org/10.1006/jctb.1995.1026 - P. Erdős and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087–1091.
- Z. Füredi, An upper bound on Zarankiewicz' problem, Combin. Probab. Comput 5 (1996) 29–33.
https://doi.org/10.1017/S0963548300001814 - Y. Hao and Q. Lin, Star-critical Ramsey numbers for large generalized fans and books, Discrete Math. 341 (2018) 3385–3393.
https://doi.org/10.1016/j.disc.2018.08.025 - J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011) 328–334.
https://doi.org/10.1016/j.dam.2010.11.007 - J. Komlós and M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, in: Bolyai Society Mathematical Studies 2, Combinatorics, Paul Erdős is Eighty, vol.2, D. Miklós, V.T. Sós, and T. Szőnyi (Ed(s)), (Keszthely (Hungary) 1993, Budapest 1996) 295–352.
- T. Kóvari, V.T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954) 50–57.
https://doi.org/10.4064/cm-3-1-50-57 - Z. Li and Y. Li, Some star-critical Ramsey numbers, Discrete Appl. Math. 181 (2015) 301–305.
https://doi.org/10.1016/j.dam.2014.09.014 - Y. Li, Y. Li and Y. Wang, Minimal Ramsey graphs on deleting stars for generalized fans and books, Appl. Math. Comput. 372 (2020) 125006.
https://doi.org/10.1016/j.amc.2019.125006 - Y. Li and Y. Li, Star-critical Ramsey numbers involving large books, Discrete Appl. Math. 327 (2023) 68–76.
https://doi.org//10.1016/j.dam.2022.12.003 - M. Liu and Y. Li, Ramsey numbers of fans and large books, Electron. J. Combin. 29 (2022) #1.52.
https://doi.org//10.37236/10742 - Y. Liu and Y. Chen, Star-critical Ramsey numbers of cycles versus wheels, Graphs Combin. 37 (2021) 2167–2172.
https://doi.org//10.1007/s00373-021-02343-4 - V. Nikiforov and C.C. Rousseau, Large generalized books are $p$-good, J. Combin. Theory Ser. B 92 (2004) 85–97.
https://doi.org/10.1016/j.jctb.2004.03.009 - C.C. Rousseau and J. Sheehan, On Ramsey numbers for books, J. Graph Theory 2 (1978) 77–87.
https://doi.org/10.1002/jgt.3190020110 - M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, in: Proc. Colloq, Tihany, 1966, P. Erdős and G. Katona (Ed(s)), (Academic Press, New York 1968) 279–319.
- E. Szemerédi, Regular partitions of graphs, in: Problémes Combinatories et Théorie des Graphs, Orsay 1976, J.C. Bermond, J.C. Fournier, M. Las Vergnas, D. Scotteau (Ed(s)), (Colloq. Internat. CNRS 260, Paris 1978) 399–401.
- Y. Wang and Y. Li, Deleting edges from Ramsey graphs, Discrete Math. 343 (2020) 111743.
https://doi.org/10.1016/j.disc.2019.111743 - Y. Wang, Y. Li and Y. Li, Ramsey numbers of several $K_{t,s}$ and a large $K_{m,n}$, Discrete Math. 345 (2022) 112987.
https://doi.org/10.1016/j.disc.2022.112987 - Y. Wu, Y. Sun and S. 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, A note on Ramsey numbers for fans, Bull. Aust. Math. Soc. 92 (2015) 19–23.
https://doi.org/10.1017/S0004972715000398 - 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