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

  • M. Borowiecki
  • I. Schiermeyer
  • E. Sidorowicz

Abstract

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)$.

Published
2005-05-06
Article Number
R20