Subdivision of graphs in R ( m K 2 , P 4 )

Heliyon. 2020 Jun 12;6(6):e03843. doi: 10.1016/j.heliyon.2020.e03843. eCollection 2020 Jun.

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 ( m K 2 , P 4 ) 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 ) K 2 , P 4 ) from graph F by subdividing the edge e four times.

Keywords: Matching; Mathematics; Path; Ramsey minimal graphs; Red-blue coloring.