Digraph Colouring and Arc-Connectivity

Abstract

The dichromatic number $\vec{\chi }(D)$ of a digraph $D$ is the minimum size of a partition of its vertices into acyclic induced subgraphs. We denote by $\lambda (D)$ the maximum local edge connectivity of a digraph $D$. Neumann-Lara proved that for every digraph $D$, $\vec{\chi }(D)\le \lambda (D)+1$. In this paper, we characterize the digraphs $D$ for which $\vec{\chi }(D)=\lambda (D)+1$. This generalizes an analogue result for undirected graph proved by Stiebitz and Toft as well as the directed version of Brooks' Theorem proved by Mohar. Along the way, we introduce a generalization of Hajós join that gives a new way to construct families of dicritical digraphs that is of independent interest.

34 pages, 11 figures