Arboricity Nearly Bounds Degeneracy

Abstract

Arboricity and degeneracy are two fundamental and closely related graph parameters that measure the sparsity of a graph. Every $k$-degenerate graph is $k$-arboric, but some $k$-arboric graphs are only $(2k-1)$-degenerate. However, every maximal $k$-arboric multigraph with $n$ vertices and every maximal $k$-degenerate multigraph with $n$ vertices has exactly $k(n-1)$ edges. These basic observations lead to a natural structural question: How far are $k$-arboric graphs from being $k$-degenerate? We answer this question by showing that: By at most a $(k-1)$-bounded-degree graph apart. More specifically, we prove that a $k$-arboric multigraph admits a $(k,k-1)$-decomposition, that is, its edges can be partitioned into two multisets such that one spans a $k$-degenerate multigraph and the other spans a multigraph with every vertex having degree at most $k-1$. Moreover, we provide a complete characterisation of all possible such decomposition types. Namely, for any integers $k\ge 1$ and $d,h\ge 0$ we show that every $k$-arboric multigraph admits a $(d,h)$-decomposition if and only if $d\ge k$ and $d+h\ge 2k-1$. Our proofs are constructive and we present a polynomial time algorithm that produces such decompositions. By contrast, we show that related decision problems for general graphs (without constraints on the arboricity) are NP-complete.