Return to Question

Let G be a multipartite graph on r classes, each containing k vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a complete bipartite graph $K_{f(k),f(k)}$ for each fixed r, with f an increasing (possibly even linear) function, but the proof eludes me so far. Google search led me to extremely results about Ramsey-type results for bipartite subgraphs, but not complete ones. Any insights are much appreciated.

Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a complete bipartite graph $K_{f(k),f(k)}$ for each fixed $r$, with $f$ an increasing (possibly even linear) function, but the proof eludes me so far. Google search led me to extremely results about Ramsey-type results for bipartite subgraphs, but not complete ones. Any insights are much appreciated.

Let G be a multipartite graph on r classes, each containing k vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a complete bipartite graph on $f(k)$ vertices for each fixed r, with f an increasing (possibly even linear) function, but the proof eludes me so far. Google search led me to extremely results about Ramsey-type results for bipartite subgraphs, but not complete ones. Any insights are much appreciated.

Let G be a multipartite graph on r classes, each containing k vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a complete bipartite graph $K_{f(k),f(k)}$ for each fixed r, with f an increasing (possibly even linear) function, but the proof eludes me so far. Google search led me to extremely results about Ramsey-type results for bipartite subgraphs, but not complete ones. Any insights are much appreciated.