Directed Borodin–Kostochka conjecture for maximum out-degree

About 1 year old · traced to

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 C3⃗⊞K↔Δ−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 C3⃗⊞K↔Δ−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.

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.