Ramsey and Gallai-Ramsey Numbers of Cycles and Books

被引：0

作者：

Mei-qin Wei ^{[1
]}

Ya-ping Mao ^{[2
]}

Ingo Schiermeyer ^{[3
]}

Zhao Wang ^{[4
]}

机构：

[1] School of Science, Shanghai Maritime University, Shanghai

[2] School of Mathematical Sciences, East China Normal University, Shanghai

[3] Academy of Plateau Science and Sustainability, and School of Mathematics and Statistis, Qinghai Normal University, Xining, Qinghai

[4] Institut für Diskrete Mathematik und Algebra, Technische Universität Bergakademie Freiberg, Freiberg

[5] College of Science, China Jiliang University, Hangzhou

来源：

Acta Mathematicae Applicatae Sinica, English Series | 2025年 / 41卷 / 2期

基金：

中国国家自然科学基金;

关键词：

05C38; 05C55; 05D10; book graph; cycle; Gallai-Ramsey number; rainbow path; Ramsey number;

D O I：

10.1007/s10255-025-0009-6

中图分类号：

学科分类号：

摘要：

Given two non-empty graphs G, H and a positive integer k, the Gallai-Ramsey number grk(G: H) is defined as the minimum integer N such that for all n ≥ N, every exact k-edge-coloring of Kn contains either a rainbow copy of G or a monochromatic copy of H. Denote grk′(G: H) as the minimum integer N such that for all n ≥ N, every edge-coloring of Kn using at most k colors contains either a rainbow copy of G or a monochromatic copy of H. In this paper, we get some exact values or bounds for grk(P5: H) and grk′(P5: H), where H is a cycle or a book graph. In addition, our results support a conjecture of Li, Besse, Magnant, Wang and Watts in 2020. © The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2025.

引用

页码：425 / 440

页数：15

共 50 条

[1] Bondy J.A., Erdos P., Ramsey numbers for cycles in graphs, J. Combin. Theory, Ser. B, 14, pp. 46-54, (1973)
[2] Bondy J.A., Murty U.S.R., Graph Theory, (2008)
[3] Bruce D., Song Z.X., Gallai-Ramsey numbers of C<sub>7</sub> with multiple colors, Discrete Math, 342, 4, pp. 1191-1194, (2019)
[4] Cameron K., Edmonds J., Lambda composition, J. Graph Theory, 26, 1, pp. 9-16, (1997)
[5] Chen M., Li Y., Pei C., Gallai-Ramsey numbers of odd cycles and complete bipartite graphs, Graphs Combin, 34, pp. 1185-1196, (2018)
[6] Cheng X., Xu Z., Euclidean Gallai-Ramsey for various configurations, Discrete Comput. Geom, (2024)
[7] Chung F.R.K., Graham R.L., On multicolor Ramsey numbers for complete bipartite graphs, J. Combin. Theory, Ser. B, 18, pp. 164-169, (1975)
[8] Diestel R., Graph Theory, (2005)
[9] Dzido T., Nowik A., Szuca P., New lower bound for multicolor Ramsey numbers for even cycles, Electronic J. Combin, 12, (2005)
[10] Erdos P., Gallai T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10, 3, pp. 337-356, (1959)

← 1 2 3 4 5 →