On Ramsey (4K2, P3)-minimal graphs

Abstract

Let F, G, and H be simple graphs. We write F → (G, H) to mean that any red–blue coloring of all edges of F will contain either a red copy of G or a blue copy of H. A graph F (without isolated vertices) satisfying F → (G, H) and for each e ∈ E(F), (F − e) ↛ (G, H) is called a Ramsey (G, H)-minimal graph. The set of all Ramsey (G, H)-minimal graphs is denoted by R(G, H). In this paper, we derive the necessary and sufficient condition of graphs belonging to R(4K2, H), for any connected graph H. Moreover, we give a relation between Ramsey (4K2, P3)- and (3K2, P3)-minimal graphs, and Ramsey (4K2, P3)- and (2K2, P3)-minimal graphs. Furthermore, we determine all graphs in R(4K2, P3). ⃝c 2017 Kalasalingam University. Publishing Services by Elsevier B.V. This is an open access article under the CC BY-NC-ND