Published in:
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 egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2010}, |
NUMBER | = | {TR-2010-08} |