An analogue of Reed's conjecture for digraphs

In 1998, Reed conjectured that every graph G satisfies χ(G) ⩽ ⌈ ∆(G)+1+ω(G) 2 ⌉, and proved that, for some ε > 0,

We propose an analogous conjecture for digraphs. Given a digraph D, we denote by ⃗ χ(D) the dichromatic number of D, which is the minimum number of colours needed to partition V (D) into sets inducing acyclic subdigraphs. A biclique is a set of vertices that are pairwise linked with two arcs in opposite directions, and ↔ ω(D) denotes the order of a largest biclique of D. We also let ∆(D) = max

⌉, which, if true, implies Reed's conjecture. As a partial result, we prove that there exists ε > 0 such that every digraph

This implies both Reed's result and an independent result of Harutyunyan and Mohar for oriented graphs.

To obtain this upper bound on ⃗ χ, we prove that every digraph D whose biclique number is larger than 2 3 (∆max(D) + 1) admits an acyclic set of vertices intersecting each maximum biclique of D, where ∆max(D) = max

This generalises a result of King. We finally give a short proof that every oriented graph D with underlying graph G satisfies both ⃗ χ(D) ⩽ √ 2 2 ∆(D) + 2 and ⃗ χ(D) ⩽ 1 3 ∆(G) + 2, improving on results of Golowich and Steiner, respectively.