﻿ 关于路和圈的3-色Ramsey数
 文章快速检索
 同济大学学报(自然科学版)  2018, Vol. 46 Issue (7): 988-990.  DOI: 10.11908/j.issn.0253-374x.2018.07.018 0

### 引用本文

CHEN Ming, LI Yusheng. On Some Three-color Ramsey Numbers of Paths and Cycles[J]. Journal of Tongji University (Natural Science), 2018, 46(7): 988-990. DOI: 10.11908/j.issn.0253-374x.2018.07.018

### 文章历史

1. 同济大学 数学科学学院，上海 200092;
2. 嘉兴学院 数理与信息工程学院，浙江 嘉兴 314000

On Some Three-color Ramsey Numbers of Paths and Cycles
CHEN Ming 1,2, LI Yusheng 1
1. School of Mathematical Sciences, Tongji University, Shanghai 200092, China;
2. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing Zhejiang 314000, China
Abstract: For given graphs G1, G2, …, Gk, where k≥2, the k-color Ramsey number R(G1, G2, …, Gk)is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, there is always a monochromatic copy of Gi colored with color i, for some 1≤ik. In this note, we provide the exact value for 3-color Ramsey R(Pm, Pm, Cn), where n is larger than m.
Key words: path    cycle    3-color Ramsey number
1 研究背景

 $R({P_m}, {P_n}, {C_k}) = 2n + 2\left\lfloor {\frac{m}{2}} \right\rfloor-3$

2 主要结果的证明

ab是正整数，定义$r(a, b) = a-b\left\lfloor {\frac{a}{b}} \right\rfloor = a\; \bmod \; b$.对于整数nk≥3，定义：$w(n, k) = \frac{1}{2}(n-1)k-\frac{1}{2}r(k-r - 1)$, 其中r=r(n-1, k-1).

2.1 定理8的证明

m≤4时，由定理5可知结论成立.以下设m≥6.

 $\frac{{N(N-1)}}{2}-2 \cdot \frac{{m-2}}{2}N > \frac{{{{(N - 1)}^2}}}{4} + 1$

 $\begin{array}{l} w(N, n-1) = \frac{1}{2}(N-1)(n-2) - \frac{1}{2}(m - 1)(n - \\ 1(m - 1) - 1) \end{array}$

 $\begin{array}{l} \frac{{N(N-1)}}{2} \le 2 \cdot \frac{{m-2}}{2}N + w(N, n-1) = \\ (m - 2)N - \frac{1}{2}(N - 1)(n - 2) - \frac{1}{2}(m\\ - 1)(n - m - 1) \end{array}$

2.2 定理9的证明

m=3时，由定理4可知结论成立.以下设m≥5.

 $\frac{{N(N-1)}}{2}-2 \cdot \frac{{m-2}}{2}N > \frac{{{{(n - 1)}^2}}}{4} + 1$

 $w\left( {N, n-1} \right) = \frac{1}{2}\left( {N-1} \right)\left( {n-2} \right) - \frac{1}{2}\left( {m - 2} \right)\left( {n - 1 - \left( {m - 2} \right) - 1} \right)$

 $\begin{array}{l} \frac{{N\left( {N-1} \right)}}{2} \le 2\cdot\frac{{m-2}}{2}N + w\left( {N, n-1} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {m - 2} \right)N + \frac{1}{2}\left( {N - 1} \right)\left( {n - 2} \right) - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{2}\left( {m - 2} \right)\left( {n - m} \right) \end{array}$

 [1] BOLLOBÁS B. Modern graph theory [M]. New York: Spring-Verlag, 1998. [2] RADZISZOWSKI S P. Small ramsey numbers[J]. Electronic Journal of Combinatorics, 2011, 1(4): 28 [3] GYÁRFS A, RUSZINKÓ M, SÁKÖZY G N, et al. Three color ramsey numbers for paths[J]. Combinatorica, 2007, 27(1): 35 DOI:10.1007/s00493-007-0043-4 [4] BENEVIDES F S, SKOKAN J. The 3-colored ramsey number of even cycles[J]. Journal of Combinatorial Theory, Series B, 2009, 99(4): 690 DOI:10.1016/j.jctb.2008.12.002 [5] KOHAYAKAWA Y, SIMONOVITS M, SKOKAN J. The 3-colored Ramsey number of odd cycles[J]. Electronic Notes in Discrete Mathematics, 2005, 19: 397 DOI:10.1016/j.endm.2005.05.053 [6] DZIDO T. Multicolor ramsey numbers for paths and cycles[J]. Discussiones Mathematicae Graph Theory, 2005, 25(1-2): 57 DOI:10.7151/dmgt [7] DZIDO T, KUBALE M, PIWAKOWSKI K. On some ramsey and turán-type numbers for paths and cycles[J]. The Electronic Journal of Combinatorics, 2006, 13: R55 [8] SHAO Zehui, XU Xiaodong, SHI Xiaolong, et al. Some three-color Ramsey numbers, R (P4, P5, Ck) and R (P4, P6, Ck)[J]. European Journal of Combinatorics, 2009, 30(2): 396 DOI:10.1016/j.ejc.2008.05.008 [9] DZIDO T, FIDYTEK R. On some three color ramsey numbers for paths and cycles[J]. Discrete Mathematics, 2009, 309(15): 4955 DOI:10.1016/j.disc.2008.04.053 [10] BRANDT S. A sufficient condition for all short cycles[J]. Discrete Applied Mathematics, 1997, 79(1-3): 63 DOI:10.1016/S0166-218X(97)00032-2 [11] CACCETTA L, VIJAYAN K. Maximal cycles in graphs[J]. Discrete Mathematics, 1991, 98(1): 1 DOI:10.1016/0012-365X(91)90407-S