A New Construction of $k$-Folkman Graphs

Abstract

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,\dots ,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 $ϵ$ and any bipartite graph $G$, there is a $k$-Folkman graph for $G$ of order $O(|V(G){|}^{3+ϵ})$ without triangles.