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_2\) 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_2\)-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.





Similar content being viewed by others
References
Chvátal, V., Harary, F.: Generalized Ramsey theory for graphs, III. Small off-diagonal numbers. Pac. J. Math. 41, 335–345 (1972)
Cockayne, E., Lorimer, P.: On Ramsey graph number for star and stripes. Can. Math. Bull. 18, 31–34 (1972)
Zhang, Y., Broersma, H., Chen, Y.: Ramsey numbers of trees versus fans. Discrete Math. 338, 994–999 (2015)
Burr, S., Erdős, P., Spencer, J.: Ramsey theorems for multiple copies of graphs. Trans. Am. Math. Soc. 209, 87–99 (1975)
Burr, S.: On the Ramsey numbers \(r(G, nH)\) and \(r(nG, nH)\) when \(n\) is large. Discrete Math. 65, 215–229 (1987)
Burr, S.: Ramsey numbers involving graphs with long suspended paths. J. Lond. Math. Soc. 24, 405–413 (1981)
Burr, S., Erdős, P.: Generalizations of a Ramsey-theoretic result of Chvátal. J. Graph Theory 7, 39–51 (1983)
Allen, P., Brightwell, G., Skokan, J.: Ramsey-goodness—and otherwise. Combinatorica 33, 125–160 (2013)
Balla, I., Pokrovskiy, A., Sudakov, B.: Ramsey goodness of bounded degree trees. Combin. Prob. Comput. 27, 289–309 (2018)
Li, Y., Rousseau, C.: Fan-complete graph Ramsey numbers. J. Graph Theory 23, 413–420 (1996)
Lin, Q., Li, Y., Dong, L.: Ramsey goodness and generalized stars. Eur. J. Combin. 31(5), 1228–1234 (2010)
Lin, Q., Peng, X.: Large book-cycle Ramsey numbers. SIAM J. Discrete Math. 35, 532–545 (2021)
Nikiforov, V., Rousseau, C.: Large generalized books are \(p\)-good. J. Combin. Theory Ser. B 92, 85–97 (2004)
Nikiforov, V., Rousseau, C.: Ramsey goodness and beyond. Combinatorica 29, 227–262 (2009)
Pokrovskiy, A., Sudakov, B.: Ramsey goodness of paths. J. Combin. Theory Ser. B 122, 384–390 (2017)
Chvátal, V.: Tree-complete graph Ramsey numbers. J. Graph Theory 1, 93 (1977)
Hu, S., Peng, Y.: The Ramsey number for a forest versus disjoint union of complete graphs. Graphs Combin. 39, 26 (2023)
Acknowledgements
We are thankful to the reviewers for reading the manuscript very carefully and giving us valuable comments to help improve the presentation.
Author information
Authors and Affiliations
Contributions
Si-Nan Hu and Yue-Jian Peng were contribute equally to the paper.
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
This work was supported by the National Natural Science Foundation of China (No. 11931002).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Hu, SN., Peng, YJ. Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs. J. Oper. Res. Soc. China 13, 297–312 (2025). https://doi.org/10.1007/s40305-023-00494-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40305-023-00494-0