TR-2010-08

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:

@techreport{egres-10-08,

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}

}