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

Previous Articles Next Articles

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

CLC Number:

05C35
05D10

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.

TrendMD

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments

[1]	Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng. Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R² Using Stock Pieces of Materials with Fixed Length [J]. Journal of the Operations Research Society of China, 2024, 12(4): 996-1021.
[2]	Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang. Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem [J]. Journal of the Operations Research Society of China, 2024, 12(3): 729-755.
[3]	Hao Lin, Cheng He. The Minimum Centroid Branch Spanning Tree Problem [J]. Journal of the Operations Research Society of China, 2024, 12(2): 528-539.
[4]	Gang Zhang, Baoyindureng Wu. 2-Independent Domination in Trees [J]. Journal of the Operations Research Society of China, 2024, 12(2): 485-494.
[5]	Lei Wang, Cui Liu, Hong-Wei Gao, Chong Lin. Irrational-Behavior-Proof Conditions for Stochastic Games over Event Trees [J]. Journal of the Operations Research Society of China, 2024, 12(1): 243-263.
[6]	Zhuo Diao. On the Vertex Cover Number of 3-Uniform Hypergraph [J]. Journal of the Operations Research Society of China, 2021, 9(2): 427-440.
[7]	Peng-Fei Wan, Xin-Zhuang Chen. Computing the Number of k-Component Spanning Forests of a Graph with Bounded Treewidth [J]. Journal of the Operations Research Society of China, 2019, 7(2): 385-394.
[8]	T. C. E. Cheng · Yin-Kui Li · Chuan-Dong Xu . Extreme Tenacity of Graphs with Given Order and Size [J]. Journal of the Operations Research Society of China, 2014, 2(3): 307-316.
[9]	Ayumi Igarashi · Yoshitsugu Yamamoto. Computational Complexity of a Solution for Directed Graph Cooperative Games [J]. Journal of the Operations Research Society of China, 2013, 1(3): 405-414.
[10]	Zhao Gu · Ji-Xiang Meng · Zhao Zhang · Jin E.Wan. Some Upper Bounds Related with Domination Number [J]. Journal of the Operations Research Society of China, 2013, 1(2): 217-.