Logic Seminar

Please note that the time is PST

A greedy algorithm argument demonstrates that any undirected graph of degree bounded by dd has chromatic number at most d+1d+1. This upper bound is sharp; the obvious obstructions to a smaller upper bound are odd cycles and complete graphs. In 1941, Brooks proved that these obstructions are the only ones: Any undirected graph of degree bounded by dd not containing odd cycles or complete graphs admits a proper dd-coloring. The determinacy argument of Marks demonstrates that there is no Borel analogue of Brooks's theorem. However, in 2016, Conley, Marks, and Tucker-Drob proved a measurable version of Brooks's theorem.

In the 1980s, combinatorialists introduced a coloring notion for directed graphs known as dicoloring. Work of Harutyunyan and Mohar resulted in a Brooks-like characterization of the directed graphs of maximum degree bounded by dd that admit dd-dicolorings. In this talk, we present and sketch a proof of a measurable version of this theorem. We explain also why the theorem has no Borel analogue.