An analogue of Reed’s conjecture for digraphs
Ken‐ichi Kawarabayashi, Lucas Picasarri‐Arrieta · Society for Industrial and Applied Mathematics eBooks · 2025
Reed in 1998 conjectured that every graph G satisfies . As a partial result, he proved the existence of ε > 0 for which every graph G satisfies . We propose an analogue 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 D into acyclic induced subdigraphs. We let denote the size of a largest biclique (a set of vertices inducing a complete digraph) of D and . We conjecture that every digraph D satisfies , which if true implies Reed’s conjecture. As a partial result, we prove the existence of ε > 0 for which every digraph D satisfies . This implies both Reed’s result and an independent result of Harutyunyan and Mohar for oriented graphs.