A New Construction of \(k\)-Folkman Graphs

Given a graph \(G\) and a positive integer \(k\), a graph \(H\) is a \(k\)-Folkman graph for \(G\) if for any map \(\pi: V(H) \to \{1, \ldots, k\}\), there is an induced subgraph of \(H\) isomorphic to \(G\) on which \(\pi\) is constant. J. Folkman ({SIAM J. Appl. Math.} 18 (1970), pp. 19-24) first showed the existence of such graphs. We provide here a new construction of \(k\)-Folkman graphs for bipartite graphs \(G\) via random hypergraphs. In particular, we show that for any fixed positive integer \(k\), any fixed positive real number \(\epsilon\) and any bipartite graph \(G\), there is a \(k\)-Folkman graph for \(G\) of order \(O(|V(G)|^{3+\epsilon})\) without triangles.