Measurable Brooks’s theorem for directed graphs
Fundamenta Mathematicae · 14.05.2026
DOI: 10.4064/fm241107-7-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Fundamenta Mathematicae, online erschienen am 14.05.2026. Verfasst von Cecelia Higgins.
Abstract (Originalsprache)
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.
Zitieren
APA
Higgins, C. (2026). Measurable Brooks’s theorem for directed graphs. Fundamenta Mathematicae. https://doi.org/10.4064/fm241107-7-4
Vancouver
Higgins C. Measurable Brooks’s theorem for directed graphs. Fundamenta Mathematicae. 2026. doi:10.4064/fm241107-7-4
BibTeX
@article{Higgins2026,
author = {Higgins, Cecelia},
title = {Measurable Brooks’s theorem for directed graphs},
journal = {Fundamenta Mathematicae},
year = {2026},
doi = {10.4064/fm241107-7-4}
}
EUVIMED