Kawarabayashi–Picasarri-Arrieta Reed-type conjecture for digraphs

About 1 year old · traced to

Let DD be a digraph. Define its maximum geometric-mean degree by

Δ~(D)=max⁡v∈V(D)d−(v)d+(v),\widetilde{\Delta}(D)=\max_{v\in V(D)}\sqrt{d^-(v)d^+(v)},

let ω↔(D)\overset{\leftrightarrow}{\omega}(D) be its biclique number, and let χ⃗(D)\vec{\chi}(D) be its dichromatic number. Kawarabayashi–Picasarri-Arrieta conjecture.

χ⃗(D)≤⌈12(Δ~(D)+1+ω↔(D))⌉.\vec{\chi}(D) \leq \left\lceil \frac{1}{2}\big(\widetilde{\Delta}(D)+1+\overset{\leftrightarrow}{\omega}(D)\big)\right\rceil.

This is a directed analogue of Reed's conjecture. The source records an intermediate result with an error parameter, but does not state that the conjecture itself is resolved.

References

Primary source

Ararat Harutyunyan, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta and Gil Puig i Surroca, “(Δ-1)-dicolouring of digraphs”, arXiv:2507.10266 (2025).

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.