Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs

doi:10.1007/s40305-023-00494-0

Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (1): 297-312.doi: 10.1007/s40305-023-00494-0

收稿日期:2022-10-15 修回日期:2023-05-09 出版日期:2025-03-30 发布日期:2025-03-20
通讯作者: Yue-Jian Peng,Si-Nan Hu E-mail:ypeng1@hnu.edu.cn;husinan7@163.com
基金资助:
This work was supported by the National Natural Science Foundation of China (No. 11931002).

Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs

Si-Nan Hu¹, Yue-Jian Peng²

1 School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha 410114, Hunan, China;
2 School of Mathematics, Hunan University, Changsha 410082, Hunan, China

Received:2022-10-15 Revised:2023-05-09 Online:2025-03-30 Published:2025-03-20
Contact: Yue-Jian Peng,Si-Nan Hu E-mail:ypeng1@hnu.edu.cn;husinan7@163.com

摘要/Abstract

Abstract: For graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any coloring of the edges of the complete graph K_N in red or blue yields a red G or a blue H. Denote the union of t disjoint copies of a graph F by tF. We call tK₂ a stripe. In this paper, we completely determine Ramsey numbers of stripes versus trees and unicyclic graphs. Our result also implies that a tree is tK₂-good if and only if the independence number of this tree is no less than t. As an application, we improve the known Ramsey numbers of stars versus fan graphs. Moreover, we determine the bipartite Ramsey numbers of a connected bipartite graph versus stripes.

Key words: Ramsey number, Bipartite Ramsey number, Stripes, Tree, Unicyclic graph

中图分类号:

05C35
05D10

. [J]. Journal of the Operations Research Society of China, 2025, 13(1): 297-312.

Si-Nan Hu, Yue-Jian Peng. Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs[J]. Journal of the Operations Research Society of China, 2025, 13(1): 297-312.

参考文献

[1] Chvátal, V., Harary, F.: Generalized Ramsey theory for graphs, III. Small off-diagonal numbers. Pac. J. Math. 41, 335-345(1972)
[2] Cockayne, E., Lorimer, P.: On Ramsey graph number for star and stripes. Can. Math. Bull. 18, 31-34(1972)
[3] Zhang, Y., Broersma, H., Chen, Y.: Ramsey numbers of trees versus fans. Discrete Math. 338, 994-999(2015)
[4] Burr, S., Erdős, P., Spencer, J.: Ramsey theorems for multiple copies of graphs. Trans. Am. Math. Soc. 209, 87-99(1975)
[5] Burr, S.: On the Ramsey numbers r(G, nH) and r(nG, nH) when n is large. Discrete Math. 65, 215-229(1987)
[6] Burr, S.: Ramsey numbers involving graphs with long suspended paths. J. Lond. Math. Soc. 24, 405-413(1981)
[7] Burr, S., Erdős, P.: Generalizations of a Ramsey-theoretic result of Chvátal. J. Graph Theory 7, 39-51(1983)
[8] Allen, P., Brightwell, G., Skokan, J.: Ramsey-goodness—and otherwise. Combinatorica 33, 125-160(2013)
[9] Balla, I., Pokrovskiy, A., Sudakov, B.: Ramsey goodness of bounded degree trees. Combin. Prob. Comput. 27, 289-309(2018)
[10] Li, Y., Rousseau, C.: Fan-complete graph Ramsey numbers. J. Graph Theory 23, 413-420(1996)
[11] Lin, Q., Li, Y., Dong, L.: Ramsey goodness and generalized stars. Eur. J. Combin. 31(5), 1228-1234(2010)
[12] Lin, Q., Peng, X.: Large book-cycle Ramsey numbers. SIAM J. Discrete Math. 35, 532-545(2021)
[13] Nikiforov, V., Rousseau, C.: Large generalized books are p-good. J. Combin. Theory Ser. B 92, 85-97(2004)
[14] Nikiforov, V., Rousseau, C.: Ramsey goodness and beyond. Combinatorica 29, 227-262(2009)
[15] Pokrovskiy, A., Sudakov, B.: Ramsey goodness of paths. J. Combin. Theory Ser. B 122, 384-390(2017)
[16] Chvátal, V.: Tree-complete graph Ramsey numbers. J. Graph Theory 1, 93(1977)
[17] Hu, S., Peng, Y.: The Ramsey number for a forest versus disjoint union of complete graphs. Graphs Combin. 39, 26(2023)

Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价