URA Seminar - Ronen Wdowinski

Tuesday, May 23, 2023 2:30 pm - 2:30 pm EDT (GMT -04:00)

Title: Bounded degree arboricity

Speaker: Ronan Wdowinski
Affiliation: University of Waterloo
Location: MC 5479

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.