An analogue of Reed's conjecture for digraphs

Reed in 1998 conjectured that every graph $G$ satisfies $\chi (G)\le \lceil \frac{\mathrm{\Delta }(G)+1+\omega (G)}{2}\rceil$. As a partial result, he proved the existence of $\epsilon >0$ for which every graph $G$ satisfies $\chi (G)\le \lceil (1-\epsilon )(\mathrm{\Delta }(G)+1)+\epsilon \omega (G)\rceil$. We propose an analogue conjecture for digraphs. Given a digraph $D$, we denote by $\vec{\chi }(D)$ the dichromatic number of $D$, which is the minimum number of colours needed to partition $D$ into acyclic induced subdigraphs. We let $\overleftrightarrow{\omega }(D)$ denote the size of the largest biclique (a set of vertices inducing a complete digraph) of $D$ and $\tilde{\mathrm{\Delta }}(D)={\max }_{v\in V(D)}\sqrt{d^{+}(v)\cdot d^{-}(v)}$. We conjecture that every digraph $D$ satisfies $\vec{\chi }(D)\le \lceil \frac{\tilde{\mathrm{\Delta }}(D)+1+\overleftrightarrow{\omega }(D)}{2}\rceil$, which if true implies Reed’s conjecture. As a partial result, we prove the existence of $\epsilon >0$ for which every digraph $D$ satisfies $\vec{\chi }(D)\le \lceil (1-\epsilon )(\tilde{\mathrm{\Delta }}(D)+1)+\epsilon \overleftrightarrow{\omega }(D)\rceil$. This implies both Reed’s result and an independent result of Harutyunyan and Mohar for oriented graphs. To obtain this upper bound on $\vec{\chi }$, we prove that every digraph $D$ with $\overleftrightarrow{\omega }(D)>\frac{2}{3}({\mathrm{\Delta }}_{\max }(D)+1)$, where ${\mathrm{\Delta }}_{\max }(D)={\max }_{v\in V(D)}\max (d^{+}(v),d^{-}(v))$, admits an acyclic set of vertices intersecting each biclique of $D$, which generalises a result of King. We finally give a short proof that all oriented graphs $D$ satisfy $\vec{\chi }(D)\le \frac{\sqrt{2}}{2}\text{Tilde}\mathrm{\Delta }(D)+2$, improving on a result of Golowich.