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

Let DD be a digraph, let

Δ~(D)=maxvV(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 C3KΔ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 C3KΔ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.

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.