View PDF HTML (experimental)

Abstract:Reed in 1998 conjectured that every graph $G$ satisfies $\chi(G) \leq \lceil \frac{\Delta(G)+1+\omega(G)}{2} \rceil$. As a partial result, he proved the existence of $\varepsilon > 0$ for which every graph $G$ satisfies $\chi(G) \leq \lceil (1-\varepsilon)(\Delta(G)+1)+\varepsilon\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{\Delta}(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We conjecture that every digraph $D$ satisfies $\vec{\chi}(D) \leq \lceil \frac{\tilde{\Delta}(D)+1+\overleftrightarrow{\omega}(D)}{2} \rceil$, which if true implies Reed's conjecture. As a partial result, we prove the existence of $\varepsilon >0$ for which every digraph $D$ satisfies $\vec{\chi}(D) \leq \lceil (1-\varepsilon)(\tilde{\Delta}(D)+1)+\varepsilon\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}(\Delta_{\max}(D)+1)$, where $\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) \leq \frac{\sqrt{2}}{2} \tilde{\Delta}(D) + 2$, improving on a result of Golowich.

Submission history

From: Lucas Picasarri-Arrieta [view email]
[v1] Mon, 8 Jul 2024 11:14:41 UTC (36 KB)
[v2] Sat, 27 Jul 2024 08:06:59 UTC (36 KB)
[v3] Wed, 27 Aug 2025 00:20:46 UTC (24 KB)
[v4] Tue, 8 Sep 2026 01:15:25 UTC (39 KB)