On Ramsey Minimal Graphs for the Pair Paths

Abstract

For any graphs G and H, we write F → (G, H) to means that in any red-blue coloring of all the edges of F, the graph F will contain either a red G or a blue H. A graph F is called a Ramsey (G,H)-minimal graph if F satisfies two conditions: F → (G, H), and F∗ -A (G, H) for every subgraph F∗ of F. The set of all Ramsey (G, H)-minimal graphs is denoted by R(G, H). In this paper, we construct some family of graphs which belong to R(P3, Pn), for any n ≥ 6. In particular, we give an infinite class of trees which provides Ramsey (P3, P7)-minimal graphs.