Kawarabayashi–Picasarri-Arrieta dichromatic bound conjecture

From papers

Let DD be a digraph. Define

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

and let tinyω(D)\overset{\text{tiny}}{\leftrightarrow}{\omega}(D) be the largest size of a biclique in DD. Let χ(D)\vec{\chi}(D) denote the dichromatic number of DD. Kawarabayashi–Picasarri-Arrieta conjecture. Every digraph DD satisfies

χ(D)12(Δ~(D)+1+tinyω(D)).\vec{\chi}(D) \leq \left\lceil \frac{1}{2}\left(\widetilde{\Delta}(D)+1+\overset{\text{tiny}}{\leftrightarrow}{\omega}(D)\right)\right\rceil.

If true, this would imply Reed's conjecture and an independent conjecture of Harutyunyan and Mohar. The conjecture is presented as open in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Ken-ichi Kawarabayashi and Lucas Picasarri-Arrieta, “Coloring digraphs with Δ-b colors”, arXiv:2607.06928 (2026).

Solutions 0

No solutions have been posted yet.