On some three-color Ramsey numbers for paths

详细信息    查看全文

• 作者：Janusz Dybizbański^a ; ^{jdybiz@inf.ug.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Tomasz Dzido^a ; ^{tdz@inf.ug.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Stanisław Radziszowski^b ; ^{spr@cs.rit.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Three-color Ramsey number ; Path graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 May 2016
• 年：2016
• 卷：204
• 期：Complete
• 页码：133-141
• 全文大小：405 K

文摘

For graphs G₁,G₂,G₃$G_1,G_2,G_3$, the three-color Ramsey number R(G₁,G₂,G₃)$R(G_1,G_2,G_3)$ is the smallest integer n$n$ such that if we arbitrarily color the edges of the complete graph of order n$n$ with 3 colors, then it contains a monochromatic copy of G_i$G_i$ in color i$i$, for some 1≤i≤3$1\le i\le 3$.

First, we prove that the conjectured equality R(C_2n,C_2n,C_2n)=4n$R(C_{2n},C_{2n},C_{2n})=4n$, if true, implies that R(P_2n+1,P_2n+1,P_2n+1)=4n+1$R(P_{2n+1},P_{2n+1},P_{2n+1})=4n+1$ for all n≥3$n\ge 3$. We also obtain two new exact values R(P₈,P₈,P₈)=14$R(P_8,P_8,P_8)=14$ and R(P₉,P₉,P₉)=17$R(P_9,P_9,P_9)=17$, furthermore we do so without help of computer algorithms. Our results agree with a formula R(P_n,P_n,P_n)=2n−2+(nmod2)$R(P_n,P_n,P_n)=2n-2+(nmod2)$ which was proved for sufficiently large n$n$ by Gyárfás, Ruszinkó, Sárközy, and Szemerédi (2007). This provides more evidence for the conjecture that the latter holds for all n≥1$n\ge 1$.