zbMATH — the first resource for mathematics

Bounded size components – partitions and transversals. (English) Zbl 1033.05083
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\).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Akiyama, J.; Chvátal, V., A short proof of the linear arboricity for cubic graphs, Bull. liber. arts sci. NMS, 2, (1981)
[2] Akiyama, J.; Exoo, G.; Harary, F., Coverings and packings in graphs II. cyclic and acyclic invariants, Math. slovaca, 30, 405-417, (1980) · Zbl 0458.05050
[3] Aldred, R.; Wormald, N., More on the linear k-arboricity of regular graphs, Australas. J. combin., 18, 97-104, (1998) · Zbl 0930.05075
[4] Alon, N.; Ding, G.; Oporowski, B.; Vertigan, D., Partitioning into graphs with only small components, J. combin. theory ser. B, 87, 231-243, (2003) · Zbl 1023.05045
[5] Alon, N.; Spencer, J.H., The probabilistic method, (1992), Wiley New York
[6] Bermond, J.; Fouquet, J.; Habib, M.; Péroche, B., On linear k-arboricity, Discrete math., 52, 123-132, (1984) · Zbl 0556.05054
[7] Bollobás, B.; Erdős, P.; Szemerédi, E., On complete subgraphs of r-chromatic graphs, Discrete math., 13, 97-107, (1975) · Zbl 0306.05121
[8] G. Ding, B. Oporowski, D. Sanders, D. Vertigan, preprint.
[9] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: A. Hajnal, R. Rado, V.T. Sós (Eds.), Infinite and Finite Sets, North-Holland, Amsterdam, pp. 609-628; Colloq. Math. Soc. János Bolyai, 10 (1975).
[10] Haxell, P., A note on vertex List colouring, Combin. probab. comput., 10, 345-348, (2001) · Zbl 0986.05042
[11] Jackson, B.; Wormald, N., On the linear k-arboricity of cubic graphs, Discrete math., 162, 293-297, (1996) · Zbl 0870.05036
[12] Lovász, L., On decomposition of graphs, Stud. sci. math. hung., 1, 237-238, (1966) · Zbl 0151.33401
[13] Thomassen, C., Two-colouring 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
[14] Yuster, R., Independent transversals in r-partite graphs, Discrete math., 176, 255-261, (1997) · Zbl 0891.05041
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.