Article in press
Authors:
Sinan Hu
School of Mathematics and Statistics, Changsha University of Science and Technology
email: husinan7@163.com
Title:
Ramsey numbers for a large tree versus multiple copies of complete graphs of different sizes
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-10-05 , Revised: 2024-01-16 , Accepted: 2024-01-16 , Available online: 2024-02-02 , https://doi.org/10.7151/dmgt.2537
Abstract:
For two graphs $G$ and $H$, let $G\cup H$ be the union of vertex-disjoint copy
of $G$ and $H$. And the Ramsey number $R(G,H)$ is the minimum integer $N$ such
that any red-blue coloring of the edges of the complete graph $K_N$ contains
either a red copy of $G$ or a blue copy of $H$. If $G$ is connected and
$v(G)\geq s(H)$, it is well known that $R(G,H) \geq (v(G)-1)(\chi(H)-1)+s(H)$,
where $\chi(H)$ is the chromatic number of $H$ and $s(H)$ is the size of the
smallest color class taken over all proper vertex-colorings of $H$ with
$\chi(H)$ colors. Burr defined a connected graph $G$ as $H$-good if the
above inequality becomes equality. In this paper, for integers $t\geq1$ and
$m_{1}\geq m_{2}\geq \cdots\geq m_{t}$, we show that if $n$ is sufficiently
large, then any tree $T_n$ is $\bigcup_{i= 1}^{t}K_{m_{i}}$-good. In particular,
we show that the condition of $n$ being sufficiently large can be relaxed when
$T_n$ is a star.
Keywords:
Ramsey number, tree, Ramsey goodness
References:
- P. Allen, G. Brightwell and J. Skokan, Ramsey-goodness–and otherwise, Combinatorica 33 (2013) 125–160.
https://doi.org/10.1007/s00493-013-2778-4 - I. Balla, A. Pokrovskiy and B. Sudakov, Ramsey goodness of bounded degree trees, Combin. Probab. Comput. 27 (2018) 289–309.
https://doi.org/10.1017/S0963548317000554 - M. Bucić and B. Sudakov, Tight Ramsey bounds for multiple copies of a graph, Adv. Comb. 1 (2023).
https://doi.org/10.19086/aic.2023.1 - S.A. Burr, Ramsey numbers involving graphs with long suspended paths, J. Lond. Math. Soc. (2) 24 (1981) 405–413.
https://doi.org/10.1112/jlms/s2-24.3.405 - S.A. Burr, On the Ramsey numbers $r(G, nH)$ and $r(nG, nH)$ when $n$ is large, Discrete Math. 65 (1987) 215–229.
https://doi.org/10.1016/0012-365X(87)90053-7 - S.A. Burr and P. Erdős, Generalizations of a Ramsey-theoretic result of Chvátal, J. Graph Theory 7 (1983) 39–51.
https://doi.org/10.1002/jgt.3190070106 - S.A. Burr and R.J. Faudree, On graphs $G$ for which all large trees are $G$-good, Graphs Combin. 9 (1993) 305–313.
https://doi.org/10.1007/BF02988318 - V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93–93.
https://doi.org/10.1002/jgt.3190010118 - V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, III. Small off-diagonal numbers, Pacific J. Math. 41 (1972) 335–345.
- D. Conlon, J. Fox and B. Sudakov, $2$-recent developments in graph Ramsey theory, in: Surveys in Combinatorics 2015, A. Czumaj, A. Georgakopoulos, D. Král, V. Lozin and O. Pikhurko (Ed(s)), (Cambridge University Press 2015) 49–118.
https://doi.org/10.1017/CBO9781316106853.003 - P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Shelp, Multipartite graph–-Sparse graph Ramsey numbers, Combinatorica 5 (1985) 311–318.
https://doi.org/10.1007/BF02579245 - J. Fox, X. He and Y. Wigderson, Ramsey goodness of books revisited, Adv. Comb. 4 (2023).
https://doi.org/10.19086/aic.2023.4 - R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey Theory (John Wiley & Sons, New York, 1990).
- A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, in: Combin.Theory Appl., P. Erdős, A. Rényi and V.T. Sós (Ed(s)), (North-Holland, London 1970) 601–623.
- P. Hall, On representatives of subsets, J. Lond. Math. Soc. (1) 10 (1935) 26–30.
https://doi.org/10.1112/jlms/s1-10.37.26 - S.-N. Hu and Y.-J Peng, The Ramsey number for a forest versus disjoint union of complete graphs, Graphs Combin. 39 (2023) 26.
https://doi.org/10.1007/s00373-023-02625-z - S.-N. Hu and Y.-J. Peng, Ramsey numbers of stripes versus trees and unicyclic graphs, J. Oper. Res. Soc. China (2023).
https://doi.org/10.1007/s40305-023-00494-0 - Q. Lin, Y. Li and L. Dong, Ramsey goodness and generalized stars, European J. Combin. 31 (2010) 1228–1234.
https://doi.org/10.1016/j.ejc.2009.10.011 - Q. Lin and X. Peng, Large book-cycle Ramsey numbers, SIAM J. Discrete Math. 35 (2021) 532–545.
https://doi.org/10.1137/21M1390566 - Z. Luo and Y.-J. Peng, A large tree is $tK_m$-good, Discrete Math. 346 (2023) 113502.
https://doi.org/10.1016/j.disc.2023.113502 - 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 - H.A. Kierstead and A.V. Kostochka, A short proof of the Hajnal-Szemerédi theorem on equitable colouring, Combin. Probab. Comput. 17 (2008) 265–270.
https://doi.org/10.1017/S0963548307008619 - A. Pokrovskiy and B. Sudakov, Ramsey goodness of paths, J. Combin. Theory Ser. B 122 (2017) 384–390.
https://doi.org/10.1016/j.jctb.2016.06.009 - S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2021) #DS1.
https://doi.org/10.37236/21 - A. Sulser and M. Trujić, Ramsey numbers for multiple copies of sparse graphs.
arXiv: 2212.02455 - Y. Zhang, H. Broersma and Y. Chen, Ramsey numbers of trees versus fans, Discrete Math. 338 (2015) 994–999.
https://doi.org/10.1016/j.disc.2015.01.030
Close