In 1975 Bollobas, ErdH os, and Szemeredi asked the following question: given positive integers $n, t, r$ with $2le tle r-1$, what is the largest minimum degree $delta(G)$ among all $r$-partite graphs $G$ with parts of size $n$ and which do not contain a copy of $K_{t+1}$? The $r=t+1$ case has attracted a lot of attention and was fully resolved by Haxell and Szab{o}, and Szab{o} and Tardos in 2006. In this paper we investigate the $r>t+1$ case of the problem, which has remained dormant for over forty years. We resolve the problem exactly in the case when $r equiv -1 pmod{t}$, and up to an additive constant for many other cases, including when $r geq (3t-1)(t-1)$. Our approach utilizes a connection to the related problem of determining the maximum of the minimum degrees among the family of balanced $r$-partite $rn$-vertex graphs of chromatic number at most $t$.
تحميل البحث