Directed Borodin–Kostochka conjecture with a biclique–directed-cycle obstruction

Let DD be a digraph, let

Δ~(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 the biclique number, and let χ⃗(D)\vec{\chi}(D) be the dichromatic number. Write C3⃗⊞K↔Δ−2\vec{C_3}\boxplus \overleftrightarrow{K}_{\Delta-2} for the digraph formed from a directed 33-cycle and a complete bidirected graph on Δ−2\Delta-2 vertices, with all arcs in both directions between the two parts. Directed Borodin–Kostochka conjecture. For every integer Δ≥9\Delta\geq 9 and every digraph DD satisfying Δ~(D)≤Δ\widetilde{\Delta}(D)\leq\Delta and ω↔(D)≤Δ−1\overset{\leftrightarrow}{\omega}(D)\leq\Delta-1,

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

unless DD contains C3⃗⊞K↔Δ−2\vec{C_3}\boxplus \overleftrightarrow{K}_{\Delta-2}. The obstruction explains why the direct directed analogue of Borodin–Kostochka fails, while the source proves the conjectured bound for sufficiently large parameters.

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.