An f-coloring generalization of linear arboricity - Ronen Wdowinski

Title: An f-coloring generalization of linear arboricity

Abstract: Given a multigraph $G$ and a function $f : V(G) \rightarrow \mathbb{Z}_{\ge 2}$, the degree-$f$ arboricity $a_f(G)$ is the minimum number of forests required to cover the edges of $G$, such that in these forests every vertex $v \in V(G)$ has degree at most $f(v)$. When $f$ is constant, Truszczynski (1991) conjectured that $a_f(G) \le \max \{\Delta_f(G) + 1, a(G)\}$ for every multigraph $G$, where $\Delta_f(G) = \max_{v \in V(G)} \lceil d(v)/f(v) \rceil$ and $a(G)$ is the usual arboricity of $G$. This is a strong generalization of the more well-known Linear Arboricity Conjecture (1980). We will show that this conjecture is false in a strong sense for general multigraphs. On the other hand, we will show that this conjecture holds asymptotically for simple graphs.