The directed degree-f arboricity conjecture

Let DD be a directed multigraph and let f:V(D)Z2f: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 af(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

Δf1+(D)=maxvV(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,

af(D)max{Δ(D),Δf1+(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.

Sources & referencesView supporting material

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.