Search

Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colors it red or blue. Builder wins by creating either a red copy of G or a blue copy of H for some fixed graphs G and H. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number r ̃ (G , H). In this paper, we prove some new general lower and upper bounds for on-line Ramsey numbers r ̃ (C 3 , P k) and r ̃ (C 4 , P k). [ABSTRACT FROM AUTHOR]

For graphs G 1 , G 2 , G 3 , the three-color Ramsey number R ( G 1 , G 2 , G 3 ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph of order n with 3 colors, then it contains a monochromatic copy of G i in color i , for some 1 ≤ i ≤ 3 . First, we prove that the conjectured equality R ( C 2 n , C 2 n , C 2 n ) = 4 n , if true, implies that R ( P 2 n + 1 , P 2 n + 1 , P 2 n + 1 ) = 4 n + 1 for all n ≥ 3 . We also obtain two new exact values R ( P 8 , P 8 , P 8 ) = 14 and 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 ) = 2 n − 2 + ( n mod 2 ) which was proved for sufficiently large 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 . [ABSTRACT FROM AUTHOR]