Bounded size components -- partitions and transversals.
type: Item
instance of: scholarly article
title: Bounded size components -- partitions and transversals.
zbMATH Open document ID: 1033.05083
DOI: 10.1016/S0095-8956(03)00031-5
author: Tibor Szabó
author: Gábor Tardos
author: Penny Haxell
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-17T00:00:00Z
review text: 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\).
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1965034
zbMATH Keywords: partition of vertex set
zbMATH Keywords: bounded size components
zbMATH Keywords: transveral
MaRDI profile type: Publication
cites work: Q3907606
cites work: Q4222072
cites work: Partitioning into graphs with only small components
cites work: Q4004078
cites work: On linear k-arboricity
cites work: On complete subgraphs of \(r\)-chromatic graphs
cites work: Q4074927
cites work: A note on vertex list colouring
cites work: On the linear \(k\)-arboricity of cubic graphs
cites work: Q5530470
cites work: Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
cites work: Independent transversals in \(r\)-partite graphs
full work available at URL: s0095-8956(03)00031-5
OpenAlex ID: W1986861105
description: scientific article; zbMATH DE number 1965034