Abstract:

A simple greedy procedure shows that the chromatic number $\chi(G)$ of a graph $G$ is upper bounded by $\Delta(G)+1$. In 1998, Reed conjectured that, in fact, $\chi(G)$ can be bounded halfway between $\Delta(G)+1$ and $\omega(G)$. As a partial result, he proved the existence of $\epsilon >0$ such that $\chi(G) \leq \lceil (1-\epsilon) (\Delta(G)+1) + \epsilon \omega(G) \rceil$, thus showing that $\chi(G)$ is indeed bounded by a convex combination of $\Delta(G)+1$ and $\omega(G)$.

In this talk, we will explore an analogous question for digraphs, where the chromatic number, the maximum degree, and the clique number of a graph are replaced respectively by the dichromatic number, the maximum geometric mean, and the biclique number of a digraph. We prove the analogue of Reed’s result, which also implies an independent result obtained by Harutyunyan and Mohar when restricted to oriented graphs.

Joint work with Ken-ichi Kawarabayashi.

Arxiv: https://arxiv.org/abs/2407.05827