On some three-color Ramsey numbers for paths
For graphs G1,G2,G3 G 1 , G 2 , G 3 , the three-color Ramsey number R(G1,G2,G3) 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 Gi G i in color i i , for some 1?i?3 1 ? i ? 3 . First, we prove that the conjectured equality R(C2n,C2n,C2n)=4n R ( C 2 n , C 2 n , C 2 n ) = 4 n , if true, implies that R(P2n+1,P2n+1,P2n+1)=4n+1 R ( P 2 n + 1 , P 2 n + 1 , P 2 n + 1 ) = 4 n + 1 for all n?3 n ? 3 . We also obtain two new exact values R(P8,P8,P8)=14 R ( P 8 , P 8 , P 8 ) = 14 and R(P9,P9,P9)=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(Pn,Pn,Pn)=2n?2+(nmod2) R ( P n , P n , P n ) = 2 n ? 2 + ( n mod 2 ) which was proved for sufficiently large n n by Gyrfs, Ruszink, Srkzy, and Szemerdi (2007). This provides more evidence for the conjecture that the latter holds for all n?1 n ? 1 .
three-color ramsey number path graph