Forbidden Subgraphs and Complete Partitions

Abstract

A graph is called an $(r,k)$-graph if its vertex set can be partitioned into $r$ parts, each having at most $k$ vertices and there is 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 or an even cycle. Some of these bounds are best possible up to a constant factor and confirm a conjecture of Axenovich and Martin in several cases.