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

Maya Nabila (Doctoral Program of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung)
Hilda Assiyatun (Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia)
Edy Tri Baskoro (Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 10, No 1 (2022): Electronic Journal of Graph Theory and Applications

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.