Partitioning into graphs with only small components (Q1405114)

The authors prove several results on edge partitions and vertex partitions of graphs into graphs with bounded size components. The main results are: (1) Every graph with maximum degree at most \(\Delta\) and tree-width at most \(k\) admits a vertex partition into two induced subgraphs \(G_1\), \(G_2\) such that each connected component of \(G_1\) and \(G_2\) has at most \(24k\Delta\) vertices, and an edge partition into two subgraphs \(H_1\), \(H_2\) such that each connected component of \(H_1\) and \(H_2\) has at most \(24k\Delta(\Delta+1)\) vertices. (2) Every graph with maximum degree \(\Delta\geq 3\) admits a vertex partition into \(\lfloor\frac{\Delta+2}{3}\rfloor\) induced subgraphs \(G_i\) such that each connected component of \(G_i\) has at most \(12\Delta^2-36\Delta+9\) vertices. (3) Every graph with maximum degree \(\Delta\geq 2\) admits an edge partition into \(\lfloor\frac{\Delta+1}{2}\rfloor\) subgraphs \(H_i\) such that each connected component of \(H_i\) has at most \(60\Delta-63\) edges. (4) For every integer \(n\), there is a planar graph of maximum degree six such that in every vertex partition and every edge partition \(\{G_1, G_2\}\), one of \(G_1\), \(G_2\) must have a connected component with at least \(n\) vertices, and there is a planar graph such that in every vertex partition \(\{G_1, G_2, G_3\}\), one of \(G_1\), \(G_2\), \(G_3\) must have a connected component with at least \(n\) vertices.