A Ramsey type problem concerning vertex colourings (Q1262327)

Let \(H\to^ v_ kG\) denote the fact that for every function \(\pi: V(H)\to \{1,...,k\}\) there is an induced subgraph \(G'\) of H with \(G'\cong G\) and \(V(G')\subseteq \pi^{-1}(i)\) for some i. Folkman has shown that for all graphs G and for all positive integers k such a graph H exists. We examine here f(G,k), the minimum order of a graph H for which \(H\to^ v_ kG\). We show that for any fixed integer \(k\geq 2\) there are positive constants \(C_ 1\) and \(C_ 2\) such that \[ C_ 1n^ 2\leq \max \{f(G,k):\quad | V(G)| =n\}\leq C_ 2n^ 2 \log^ 2 n. \]