Degree bounded forest covering

Tamás Király, Lap Chi Lau

Published in:
Proceedings of 15th International Conference IPCO 2011, LNCS 6655 (2011), 315-323


We prove that for an undirected graph with arboricity at most $k+\epsilon$, its edges can be decomposed into $k$ forests and a subgraph with maximum degree $\lceil \frac{k \epsilon +1}{1-\epsilon} \rceil$. The problem is solved by a linear programming based approach: we first prove that there exists a fractional solution to the problem, and then use a result on the degree bounded matroid problem by Király, Lau and Singh [5] to get an integral solution.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap},
TITLE = {Degree bounded forest covering},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-08}

Last modification: 29.12.2020. Please email your comments to Tamás Király!