Ramsey ($K_{1,2},K_3$)-Minimal Graphs

M. Borowiecki, I. Schiermeyer, E. Sidorowicz


For graphs $G,F$ and $H$ we write $G\rightarrow (F,H)$ to mean that if the edges of $G$ are coloured with two colours, say red and blue, then the red subgraph contains a copy of $F$ or the blue subgraph contains a copy of $H$. The graph $G$ is $(F,H)$-minimal (Ramsey-minimal) if $G\rightarrow (F,H)$ but $G'\not\rightarrow (F,H)$ for any proper subgraph $G'\subseteq G$. The class of all $(F,H)$-minimal graphs shall be denoted by $R (F,H)$. In this paper we will determine the graphs in $R(K_{1,2},K_3)$.

Full Text: PDF