On an $f$-coloring generalization of linear arboricity of multigraphs
Preprint
Abstract
Given a multigraph $G$ and function $f : V(G) \rightarrow \mathbb{Z}_{\ge 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 $a_f(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 $a_f(G) \le \max \{Δ_f(G) + 1, a(G)\}$ for every multigraph $G$, where $Δ_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 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.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- An Improved Bound for the Linear Arboricity ConjectureCombinatorica, 2023
- Linear arboricity of degenerate graphsJournal of Graph Theory, 2023
- Orientation‐based edge‐colorings and linear arboricity of multigraphsJournal of Graph Theory, 2022
- Linear arboricity of regular digraphsActa Mathematica Sinica, English Series, 2016
- The linear arboricity of planar graphs of maximum degree seven is fourJournal of Graph Theory, 2008
- Extremal Problems For Transversals In Graphs With Bounded DegreeCombinatorica, 2006
- Linear Arboricity and Linear k-Arboricity of Regular GraphsGraphs and Combinatorics, 2001
- Linear arboricity of digraphsNetworks, 1987
- The linear arboricity of some regular graphsJournal of Graph Theory, 1984
- Covering and packing in graphs IV: Linear arboricityNetworks, 1981