Equitable Colorings of Borel Graphs

Abstract

Hajnal and Szemerédi proved that if $G$ is a finite graph with maximum degree $\Delta$, then for every integer $k⩾\Delta +1$, $G$ has a proper coloring with $k$ colors in which every two color classes differ in size at most by $1$; such colorings are called equitable. We obtain an analog of this result for infinite graphs in the Borel setting. Specifically, we show that if $G$ is an aperiodic Borel graph of finite maximum degree $\Delta$, then for each $k⩾\Delta +1$, $G$ has a Borel proper $k$-coloring in which every two color classes are related by an element of the Borel full semigroup of $G$. In particular, such colorings are equitable with respect to every $G$-invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $\Delta$-colorings of graphs with small average degree. Namely, we prove that if $\Delta ⩾3$, $G$ does not contain a clique on $\Delta +1$ vertices, and $\mu$ is an atomless $G$-invariant probability measure such that the average degree of $G$ with respect to $\mu$ is at most $\Delta /5$, then $G$ has a $\mu$-equitable $\Delta$-coloring. As steps towards the proof of this result, we establish measurable and list coloring extensions of a strengthening of Brooks's theorem due to Kostochka and Nakprasit.

32 pages, 4 figures

References in corpus (1)

• Decompositions and measures on countable Borel equivalence relations