Abstract
A graph is called an $(r,k)$-graph if its vertex set can be partitioned into
$r$ parts of size at most $k$ with at least one edge between any two parts. Let
$f(r,H)$ be the minimum $k$ for which there exists an $H$-free $(r,k)$-graph.
In this paper we build on the work of Axenovich and Martin, obtaining improved
bounds on this function when $H$ is a complete bipartite graph, even cycle, or
tree. Some of these bounds are best possible up to a constant factor and
confirm a conjecture of Axenovich and Martin in several cases. We also
generalize this extremal problem to uniform hypergraphs and prove some initial
results in that setting.