Veröffentlichung

Titel:

Induced arboricity: Regular graphs and NP-completeness

AutorInnen:

Laurin Benz
Jonathan Rollin

Kategorie:

Arbeitspapiere

erschienen in:

eingereicht

Abstract:

We prove that for each fixed k > 1 it is NP-hard to decide whether the edge set of a graph G can be covered by k subsets of edges such that each subset forms an induced forest in G. The problem stays NP-hard when restricted to bipartite input graphs and, in case 2 <= k <= 4, restricted to planar inputs. The smallest number k that makes such a cover possible is known as the induced arboricity of a graph. We also initiate studying the induced arboricity of regular graphs: For d-regular graphs we prove that their induced arboricity is at least d and, in case d >= 3, at most 2(d-1)². The lower bound is tight and in case d <= 4 we improve the upper bound to d(d+1)/2 which is tight.