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:
@techreport{egres-10-08,
AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap}, |
TITLE | = | {Degree bounded forest covering}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2010}, |
NUMBER | = | {TR-2010-08} |