Directed Borodin–Kostochka conjecture with a biclique–directed-cycle obstruction
Directed Borodin–Kostochka conjecture with a biclique–directed-cycle obstruction
Let be a digraph, let
let be the biclique number, and let be the dichromatic number. Write for the digraph formed from a directed -cycle and a complete bidirected graph on vertices, with all arcs in both directions between the two parts. Directed Borodin–Kostochka conjecture. For every integer and every digraph satisfying and ,
unless contains . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.