Digraph Colouring and Arc-Connectivity

MaRDI QIDQ6432653zbMATH OpenFDO

Authors Pierre Aboulker, Guillaume Aubian, Pierre Charbit

Publication date 10 April 2023

Abstract: The dichromatic number $vecchi(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$, $vecchi(D)leqlambda(D)+1$. In this paper, we characterize the digraphs $D$ for which $vecchi(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'os join that gives a new way to construct families of dicritical digraphs that is of independent interest.

This page was built for publication: Digraph Colouring and Arc-Connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432653)