On Three-Color Ramsey Number of Paths

Abstract

For given graphs G1,G2,…,Gt, the multicolor Ramsey number R(G1,G2,…,Gt) 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 H1,H2,…,Ht, then at least one Hi has a subgraph isomorphic to Gi. In this paper, we show that if (n,m)≠(3,3),(3,4) and m≥n, then R(P3,Pn,Pm)=R(Pn,Pm)=m+⌊n2⌋-1. Consequently, R(P3,mK2,nK2)=2m+n-1 for m≥n≥3. © 2015, Springer Japan.