×

A note on a triangle-free – complete graph induced Ramsey number. (English) Zbl 0978.05053

Summary: The induced Ramsey number is equal to \(p\) if there exists a graph \(F\) on \(p\) vertices such that any 2-colouring of its edges with red and blue leads to either an induced copy \(G\) in the subgraph of \(F\) spanned by the red edges or an induced blue \(H\), and, furthermore, no graph on \(p-1\) vertices has the above property. We show that the lower bound of the induced Ramsey number for a triangle-free graph on \(t\) vertices and a complete graph \(K_n\) is roughly \(n^2t/4\). In one case, when the triangle-free graph is a star, a simple proof of the exact value (about \(n^2t/2\)) is given.

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI