2019/08/27 by Anton Bernshteyn, Bernshteyn, Anton, Clinton T. Conley +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #math.CO #math.LO
paper · pdf · doi:10.48550/arxiv.1908.10475
32 pages, 4 figures
openalex publication_date 2019/08/27 · arxiv created 2021/10/01 · arxiv updated 2021/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hajnal and Szemerédi proved that if G is a finite graph with maximum degree Δ, then for every integer k \geqslant Δ+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 Δ, then for each k \geqslant Δ+ 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 Δ-colorings of graphs with small average degree. Namely, we prove that if Δ\geqslant 3, G does not contain a clique on Δ+ 1 vertices, and μ is an atomless G-invariant probability measure such that the average degree of G with respect to μ is at most Δ/5, then G has a μ-equitable Δ-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.