Séminaire

Date : 4 mai 2023 13:30 - Salle :Amphi 3 - Pôle commun Digraph colouring and arc-connectivity Pierre ABOULKER, Maître de conférences - ENS Paris

The *dichromatic number* of a digraph D is the minimum size of a partition of its vertices into acyclic induced subgraphs. Even if at first glance it might look like an artificial definition, it actually generalises the usual notion of chromatic number and more and more efforts are made to extend colouring results from undirected graphs to directed graphs via this notion. The results presented here participate in this effort. *Arc connectivity* of two vertices x and y is the maximum number of directed path from x to y, and the *maximum local arc connectivity* of D is the maximum of this value taken over all pairs of vertices. Neumann-Lara proved that for every digraph the dichromatic number is at most the maximum local arc-connectivity + 1. In this talk, we characterize the digraphs for which equality holds. 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 Hajos join that gives a new way to construct families of k-critical digraphs (that is minimal digraph with dichromatic number k) that might be of independent interest.

https://www.di.ens.fr/~paboulker/