×

Ramsey \((K_ {1,2},K_ 3)\)-minimal graphs. (English) Zbl 1081.05071

If \(G,F\) and \(H\) are arbitrary graphs then the notation \(G\rightarrow(F,H)\) means, that for any 2-colouring of the edges of \(G\) either the first colour contains a copy of \(F\) or \(H\) is a subgraph of the graph induced by the second colour. A graph \(G\) is called \((F,H)\)-Ramsey-minimal if \(G\rightarrow(F,H)\) but \(G^*\not\rightarrow(F,H)\) for any proper subgraph \(G^*\) of \(G\). The class of all \((F,H)\)-Ramsey minimal graphs is denoted by \(R(F,H)\).
The paper contains a complete characterisation of the class \(R(K_{1,2},K_3)\). The proof of the main result is based on a few structural lemmas that provide necessary conditions for the graphs belonging to \(R(K_{1,2},K_3)\).

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS