{"id":"arxiv/2608.15701","url":"https://arxiv.org/abs/2608.15701","tags":["math.CO"],"score":0,"title":"Arboricity Nearly Bounds Degeneracy","domain":"math.CO","source":"arxiv","authors":["Michał Lasoń","Bartłomiej Bosek","Grzegorz Gutowski","Jakub Przybyło"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-16","reactions":{}}