Ramsey minimal graphs for a pair of a cycle on four vertices and an arbitrary star

Abstract

Let F, G and H be simple graphs. The notation F → (G, H) means that for any red-blue coloring on the edges of graph F, there exists either a red copy of G or a blue copy of H. A graph F is called a Ramsey (G, H)-minimal graph if it satisfies two conditions: (i) F → (G, H) and (ii) F − e ↛ (G, H) for any edge e of F. In this paper, we give some finite and infinite classes of Ramsey (C4, K1, n)-minimal graphs for any n ≥ 3.

Keywords

• ramsey minimal graph, cycle, star