ON RAMSEY (2K_2, 2P_n)--MINIMAL GRAPHS

摘要

Let G and H be two given graphs. The notation F → (G,H) means that any red-blue coloring on the edges of F will create either a red subgraph G or a blue subgraph H in F. A graph F is a Ramsey (G,H)-minimal graph if F satisfies two conditions: (1) F → (G,H), and (2) F~* → (G,H) for any proper subgraph F~* (is contained in) F. Denote by R(G,H) the set of all (G,H)-minimal graphs. In this paper, we give necessary conditions for the members of R(2K_2,2P_n) for n≥3. We prove that 3P_n and F(union)G are the only disconnected graphs in R(2K_2,2P_n) for any connected graphs F, G ∈ R(2K_2,P_n). In particular, we determine all graphs in R(2K_2,2P_3).