Coloring digraphs with $\hat{I}”-b$ colors

Abstract

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 $\hat{I}”(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 $\hat{I}”(D)=\hat{I}”$ being sufficiently large with respect to $b$ either contains a biclique whose size exceeds $\hat{I}”-2b$ or has dichromatic number at most $\hat{I}”-b$. This extends a classical result of Reed to the directed setting and supports a conjecture of the present authors. Furthermore, the theorem is tight, as for all integers $b$ and $\hat{I}”\ge 3b$ there exists a digraph $D$ with $\hat{I}”(D)=\hat{I}”$, dichromatic number $\hat{I}”-b+1$, and whose largest biclique has size $\hat{I}”-2b+1$.