On Three-Color Ramsey Number of Paths

摘要

For given graphs G(1), G(2),..., G(t), the multicolor Ramsey number R(G(1), G(2),..., G(t)) is the smallest positive integer n, such that if the edges of the complete graph Kn are partitioned into t disjoint color classes giving t graphs H-1, H-2,..., H-t, then at least one Hi has a subgraph isomorphic to G(i). In this paper, we show that if (n, m) not equal (3, 3), (3, 4) and m >= n, then R(P-3, P-n, P-m) = R(P-n, P-m) = m + n/2 - 1. Consequently, R(P-3, mK(2), nK(2)) = 2m + n - 1 for m >= n >= 3.