Bounded size components -- partitions and transversals. (Q1400964)

The authors prove that there is an absolute constant \(C\) such that the vertex set of every graph with maximum degree \(5\) can be partitioned into \(2\) parts such that the subgraph induced by each part does not have a component of size larger than \(C\). This way they solve a problem posed by Alon at al. Moreover, they show that the vertex set of every graph with maximum degree 4 can be partitioned into 2 parts such that the subgraph induced by each part does not have a component of size larger than \(6\). The next result says that it is possible to partition the vertex set of a graph with maximum degree at most 8 into 3 parts such that each part induces components of size at most an absolute constant \(C\). Results concerning partitions of graphs of a given maximum degree into \(k\) parts (\(k>2\)) are given too. Finally, the authors prove that if the vertex set of a graph \(G\) is partitioned into subsets of size at least \(\Delta +\lfloor\Delta / r\rfloor\) (where \(\Delta\) is the maximum degree of \(G\)) then there exists a transversal for this partition that induces in \(G\) a subgraph with all components bounded in size by \(r\).