Subdivision of graphs in R(mK2,P4)

Abstract

For any graphs F,G, and H, the notation F→(G,H) means that any red-blue coloring of all edges of F will contain either a red copy of G or a blue copy of H. The set R(G,H) consists of all Ramsey (G,H)-minimal graphs, namely all graphs F satisfying F→(G,H) but for each e∈E(F), (F−e)↛(G,H). 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 F∈R(mK2,P4) and let e∈E(F) be an edge contained in a cycle of F, we construct a new Ramsey minimal graph in R((m+1)K2,P4) from graph F by subdividing the edge e four times.

Keywords

• Mathematics
• Ramsey minimal graphs
• Red-blue coloring
• Matching
• Path