URA Seminar - Ronen Wdowinski

Title: Bounded degree arboricity

Abstract: For a multigraph $G$ together with a positive weight $f(v)$ on every vertex $v$, we study the problem of covering the edge set of $G$ by the minimum number of forests $F$ in which every vertex $v$ has degree at most $f(v)$ in $F$. We call this minimum number the degree-$f$ arboricity of $G$. We will discuss a decomposition method that has recently been used to approximate the degree-$f$ arboricity, paying particular attention to the case $f = 2$ more commonly known as linear arboricity.