Digraph Colouring and Arc-Connectivity
share
The dichromatic number χ⃗(D) of a digraph D is the minimum size of a partition of its vertices into acyclic induced subgraphs. We denote by λ(D) the maximum local edge connectivity of a digraph D. Neumann-Lara proved that for every digraph D, χ⃗(D) ≤λ(D) + 1. In this paper, we characterize the digraphs D for which χ⃗(D) = λ(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.
READ FULL TEXT