All unicyclic Ramsey (mK2, P4)-minimal graphs

Abstract

For graphs F, G and H, we write F → (G, H) to mean that if the edges of F are colored with two colors, say red and blue, then the red subgraph contains a copy of G or the blue subgraph contains a copy of H. The graph F is called a Ramsey (G, H) graph if F → (G, H). Furthermore, the graph F is called a Ramsey (G, H)-minimal graph if F → (G, H) but F − e 6→ (G, H) for any edge e ∈ E(F). In this paper, we characterize all unicyclic Ramsey (G, H)-minimal graphs when G is a matching mK2 for any integer m ≥ 2 and H is a path on four vertices.