Bounded size components—partitions and transversals

Answering a question of Alon et al., we show that there exists an absolute constant C such that every graph G with maximum degree 5 has a vertex partition into 2 parts, such that the subgraph induced by each part has no component of size greater than C. We obtain similar results for partitioning graphs of given maximum degree into k parts (k>2) as well. A related theorem is also proved about transversals inducing only small components in graphs of a given maximum degree.