2023/01/24 by Ronen Wdowinski, Wdowinski, Ronen · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2301.09933
openalex publication_date 2023/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a multigraph G and function f : V(G) → ℤ≥ 2 on its vertices, a degree-f subgraph of G is a spanning subgraph in which every vertex v has degree at most f(v). The degree-f arboricity af(G) of G is the minimum number of colors required to edge-color G into degree-f forests. At least for constant f, Truszczyński conjectured that af(G) ≤ max \Δf(G) + 1, a(G)\ for every multigraph G, where Δf(G) = maxv ∈ V(G) \lceil d(v)/f(v) \rceil and a(G) is the usual arboricity of G. This is a strong generalization of the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary. In this paper, we disprove Truszczyński's conjecture in a strong sense for general multigraphs. On the other hand, extending known results for linear arboricity, we prove that the conjecture holds for simple graphs with sufficiently large girth, and that it holds for all simple graphs asymptotically. More strongly, we prove these partial results in the setting of directed graphs, where the color classes are required to be analogously defined degree-f branchings.