Directed Borodin–Kostochka conjecture for maximum out-degree

Let DD be a digraph with maximum out-degree Δ+(D)\Delta^+(D), biclique number ω(D)\overset{\leftrightarrow}{\omega}(D), and dichromatic number χ(D)\vec{\chi}(D). Write C3KΔ2\vec{C_3}\boxplus \overleftrightarrow{K}_{\Delta-2} for the directed-cycle obstruction described above. Maximum-out-degree directed Borodin–Kostochka conjecture. If Δ+(D)=Δ9\Delta^+(D)=\Delta\geq 9 and ω(D)Δ1\overset{\leftrightarrow}{\omega}(D)\leq\Delta-1, then

χ(D)Δ1\vec{\chi}(D)\leq\Delta-1

unless DD contains C3KΔ2\vec{C_3}\boxplus \overleftrightarrow{K}_{\Delta-2}. This conjecture is presented as a stronger-parameter analogue of the preceding directed conjecture; the source proves the corresponding result for sufficiently large maximum out-degree but leaves the conjecture open.

Sources & referencesView supporting material

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.