On Ramsey Minimal Graphs for a 3-Matching Versus a Path on Five Vertices

Abstract

Let 𝐺, 𝐻, and 𝐹 be simple graphs. The notation 𝐹 ⟶ (𝐺, 𝐻) means that any red-blue coloring of all edges of 𝐹 contains a red copy of 𝐺 or a blue copy of 𝐻. The graph 𝐹 satisfying this property is called a Ramsey (𝐺, 𝐻)-graph. A Ramsey (𝐺, 𝐻)-graph is called minimal if for each edge 𝑒 ∈ 𝐸(𝐹), there exists a red-blue coloring of 𝐹 − 𝑒 such that 𝐹 − 𝑒 contains neither a red copy of 𝐺 nor a blue copy of 𝐻. In this paper, we construct some Ramsey (3𝐾2 , 𝑃5 )-minimal graphs by subdivision (5 times) of one cycle edge of a Ramsey (2𝐾2 , 𝑃5 )-minimal graph. Next, we also prove that for any integer 𝑚 ≥ 3, the set 𝑅(𝑚𝐾2 , 𝑃5) contains no connected graphs with circumference 3