A note on a triangle-free - complete graph induced Ramsey number

摘要

The induced Ramsey number, IR(B, H), 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 graphs on p - 1 vertices have the above property. There will be shown 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) will be given.