Partitioning into graphs with only small components.

*(English)*Zbl 1023.05045The 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.

(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.

Reviewer: Van Bang Le (Rostock)

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

PDF
BibTeX
XML
Cite

\textit{N. Alon} et al., J. Comb. Theory, Ser. B 87, No. 2, 231--243 (2003; Zbl 1023.05045)

Full Text:
DOI

##### References:

[1] | Alon, N., The linear arboricity of graphs, Israel J. math., 62, 311-325, (1988) · Zbl 0673.05019 |

[2] | Alon, N.; Spencer, J., The probabilistic method, (1992), Wiley New York |

[3] | Alon, N.; Teague, V.J.; Wormald, N.C., Linear arboricity and linear k-arboricity of regular graphs, Graphs combin., 17, 11-16, (2001) · Zbl 0982.05079 |

[4] | M. DeVos, G. Ding, B. Oporowski, B. Reed, D.P. Sanders, P. Seymour, D. Vertigan, Excluding any graph as a minor allows a low tree-width 2-coloring, preprint. · Zbl 1042.05036 |

[5] | Ding, G.; Oporowski, B., On tree-partitions of graphs, Discrete math., 149, 45-58, (1996) · Zbl 0844.05078 |

[6] | G. Ding, B. Oporowski, D.P. Sanders, D. Vertigan, Partitioning into graphs with only small components, preprint. · Zbl 1023.05045 |

[7] | Erdős, P.; Sachs, H., Reguläre graphen gegebener taillenweite mit minimaler knotenzahl, Wiss. Z. matin-luther-univ. halle-Wittenberg math.-natur. reihe, 12, 251-257, (1963) · Zbl 0116.15002 |

[8] | P.E. Haxell, A note on vertex list coloring, preprint. |

[9] | Hochberg, R.; McDiarmid, C.; Saks, M., On the bandwidth of triangulated triangles, Discrete math., 138, 261-265, (1995) · Zbl 0823.05048 |

[10] | Lovász, L., On decomposition of graphs, Stud. sci. math. hung., 1, 237-238, (1966) · Zbl 0151.33401 |

[11] | Petersen, J., Die theorie der regulären graphen, Acta math., 15, 193-220, (1891) · JFM 23.0115.03 |

[12] | Thomassen, C., Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5, J. combin. theory ser. B, 75, 100-109, (1999) · Zbl 0930.05043 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.