Wydawnictwa / Czasopisma IMPAN / Fundamenta Mathematicae / Wszystkie zeszyty

Streszczenie

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 \geq 3$, then unless $D$ contains the complete symmetric directed graph on $d + 1$ vertices, $D$ admits a $\mu $-measurable $d$-dicoloring with respect to any Borel probability measure $\mu $ on $X$, and $D$ admits a $\tau $-Baire-measurable $d$-dicoloring with respect to any Polish topology $\tau $ 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.