Partitioning a graph into degenerate subgraphs
Journal article, Peer reviewed
Published version
Åpne
Permanent lenke
https://hdl.handle.net/11250/2740699Utgivelsesdato
2020-01Metadata
Vis full innførselSamlinger
- Department of Informatics [981]
- Registrations from Cristin [10402]
Sammendrag
Let G = (V, E) be a connected graph with maximum degree k ≥ 3
distinct from Kk+1. Given integers s ≥ 2 and p1, . . . , ps ≥ 0, G
is said to be (p1, . . . , ps)-partitionable if there exists a partition
of V into sets V1, . . . , Vs such that G[Vi] is pi-degenerate for i ∈
{1, . . . , s}. In this paper, we prove that we can find a (p1, . . . , ps)-
partition of G in O(|V| + |E|)-time whenever 1 ≥ p1, . . . , ps ≥ 0
and ∑si=1pi ≥ k − s. This generalizes a result of Bonamy et al.
(2017) and can be viewed as an algorithmic extension of Brooks’
Theorem and several results on vertex arboricity of graphs of
bounded maximum degree. We also prove that deciding whether
G is (p, q)-partitionable is NP-complete for every k ≥ 5 and
pairs of non-negative integers (p, q) such that (p, q) ̸= (1, 1) and
p + q = k − 3. This resolves an open problem of Bonamy et al.
(2017). Combined with results of Borodin et al. (2000), Yang and
Yuan (2006) and Wu et al. (1996), it also settles the complexity
of deciding whether a graph with bounded maximum degree can
be partitioned into two subgraphs of prescribed degeneracy.