On Ramsey (mK2, P4)-Minimal Graphs

Abstract

Let 𝐹, 𝐺, and 𝐻 be simple graphs. The notation 𝐹 → (𝐺, 𝐻) means that any red-blue coloring of all edges of 𝐹 will contain either a red copy of 𝐺 or a blue copy of 𝐻. Graph 𝐹 is a Ramsey (𝐺, 𝐻)-minimal if 𝐹 → (𝐺, 𝐻) but for each 𝑒 ∈ 𝐸(𝐹), (𝐹 − 𝑒) ↛ (𝐺, 𝐻). The set ℛ(𝐺, 𝐻) consists of all Ramsey (𝐺, 𝐻)-minimal graphs. Let 𝑚𝐾2 be matching with m edges and 𝑃𝑛 be a path on n vertices. In this paper, we construct all disconnected Ramsey minimal graphs, and found some new connected graphs in ℛ(3𝐾2 , 𝑃4 ). Furthermore, we also construct new Ramsey minimal graphs in ℛ((𝑚 + 1)𝐾2 , 𝑃4) from Ramsey minimal graphs in ℛ(𝑚𝐾2 , 𝑃4) for 𝑚 ≥ 4, by subdivision operation.