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 KN 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 tK2 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 tK2-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.
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
.
DOI: 10.1007/s40305-023-00494-0
[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)
