Id: arxiv/2607.06928 Url: https://arxiv.org/abs/2607.06928 Tags: math.CO, cs.DM Score: 0 Title: Coloring digraphs with $Δ-b$ colors Domain: math.CO Source: arxiv Authors: Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-08 Page: https://delphi.science/r/arxiv/2607.06928 The dichromatic number of a digraph is the minimum number of colors needed to partition its vertex set into acyclic subdigraphs. A biclique is a set of vertices inducing all possible pairs of opposite arcs. For a digraph $D$, define $Δ(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We prove that, for every fixed integer $b\in\mathbb{N}$, every digraph $D$ with $Δ(D) = Δ$ being sufficiently large with respect to $b$ either contains a biclique whose size exceeds $Δ-2b$ or has dichromatic number at most $Δ-b$. This extends a classical result of Reed to the directed setting and supports a…