Ramsey \((K_{1,2},C_{4})\)-Minimal Graphs

Edy Tri Baskoro1, Lyra Yulianti1,2, Hilda Assiyatun2
1Combinatorial Mathematics Research Division, Faculty of Mathematics and Natural Science, Institut Teknologi Bandung, Ji. Ganesha 10 Bandung, Indonesia
2Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Andalas, Kampus UNAND Limau Manis Padang, Indonesia

Abstract

For any given graphs \( G \) and \( H \), we write \( F \rightarrow (G, H) \) to mean that any red-blue coloring of the edges of \( F \) contains a red copy of \( G \) or a blue copy of \( H \). A graph \( F \) is \((G, H)\)-minimal (Ramsey-minimal) if \( F \rightarrow (G, H) \) but \( F^* \not\rightarrow (G, H) \) for any proper subgraph \( F^* \subset F \). The class of all \((G, H)\)-minimal graphs is denoted by \( \mathcal{R}(G, H) \). In this paper, we will determine the graphs in \( \mathcal{R}(K_{1,2}, C_4) \).