Subdivision of Graphs in R(mK2,P4)

Abstract

For any graphs 𝐹 ,𝐺, and 𝐻, the notation 𝐹 → (𝐺,𝐻) means that any red-blue coloring of all edges of 𝐹 will contain either a red copy of 𝐺 or a blue copy of 𝐻. The set (𝐺,𝐻) consists of all Ramsey (𝐺,𝐻)-minimal graphs, namely all graphs 𝐹 satisfying 𝐹 → (𝐺,𝐻) but for each 𝑒 ∈ 𝐸(𝐹), (𝐹 − 𝑒) ↛ (𝐺,𝐻). In this paper, we propose a simple construction for creating new Ramsey minimal graphs from the previous known Ramsey minimal graphs (by subdivision operation). In particular, suppose 𝐹 ∈ (𝑚𝐾2,𝑃4) and let 𝑒 ∈ 𝐸(𝐹) be an edge contained in a cycle of 𝐹, we construct a new Ramsey minimal graph in ((𝑚 + 1)𝐾2,𝑃4) from graph 𝐹 by subdividing the edge 𝑒 four times.