The directed degree-f arboricity conjecture

At least 2 years old · documented by

Let DD be a directed multigraph and let f:V(D)→Z≥2f:V(D)\to\mathbb{Z}_{\ge 2} be a vertex function. A degree-ff branching is a branching in which every vertex vv has outdegree at most f(v)−1f(v)-1; let a⃗f(D)\vec{a}_f(D) be the minimum number of colors needed to partition the arcs of DD into degree-ff branchings. Write D‾\overline{D} for the underlying undirected multigraph, define

Δf−1+(D)=max⁡v∈V(D)⌈d+(v)f(v)−1⌉,\Delta_{f-1}^+(D)=\max_{v\in V(D)}\left\lceil\frac{d^+(v)}{f(v)-1}\right\rceil,

and let Δ−(D)\Delta^-(D) be the maximum indegree and a(D‾)a(\overline{D}) the arboricity of D‾\overline{D}.

Directed degree-ff arboricity conjecture. For every directed multigraph DD,

a⃗f(D)≤max⁡{Δ−(D),Δf−1+(D),a(D‾)}+1.\vec{a}_f(D)\le\max\{\Delta^-(D),\Delta_{f-1}^+(D),a(\overline{D})\}+1.

This is proposed as a natural generalization of the updated Directed Linear Arboricity Conjecture and the preceding degree-ff results. The source gives no resolution.

References

Primary source

Ronen Wdowinski, “On an f-coloring generalization of linear arboricity of multigraphs”, arXiv:2301.09933 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.