Measurable Brooks’s theorem for directed graphs

We prove a descriptive version of Brooks’s theorem for directed graphs. In particular, we show that, if D is a Borel directed graph on a standard Borel space X such that the maximum degree of each vertex is at most d≥3, then unless D contains the complete symmetric directed graph on d+1 vertices, D admits a μ-measurable d-dicoloring with respect to any Borel probability measure μ on X, and D admits a τ-Baire-measurable d-dicoloring with respect to any Polish topology τ compatible with the Borel structure on X. We also prove a definable version of Gallai’s theorem on list dicolorings by showing that any Borel directed graph of bounded degree whose connected components are not Gallai trees is Borel degree-list-dicolorable.