Equitable colourings of Borel graphs

DOI10.1017/FMP.2021.12zbMATH Open1480.05050arXiv1908.10475OpenAlexW3216555012MaRDI QIDQ5014071FDOQ5014071

Authors: Anton Bernshteyn, Clinton T. Conley 

Publication date: 6 December 2021

Published in: Forum of Mathematics, Pi (Search for Journal in Brave)

Abstract: Hajnal and Szemer'{e}di proved that if $G$ is a finite graph with maximum degree $Delta$, then for every integer $kgeqslantDelta+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 $kgeqslantDelta+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 $Deltageqslant3$, $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.

Full work available at URL: https://arxiv.org/abs/1908.10475

Recommendations

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• On equitable \(\Delta\)-coloring of graphs with low average degree
• Equitable and list equitable colorings of graphs with bounded maximum average degree.
• Measurable versions of Vizing's theorem
• A fast algorithm for equitable coloring

zbMATH Keywords

Borel measureequitable coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Infinite graphs (05C63)

Cites Work

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Title not available (Why is that?)
• Title not available (Why is that?)
• Topics in orbit equivalence
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Structure of Hyperfinite Borel Equivalence Relations
• Title not available (Why is that?)
• Equitable coloring and the maximum degree
• Groups of Automorphisms of Borel Spaces
• A fast algorithm for equitable coloring
• On equitable \(\Delta\)-coloring of graphs with low average degree
• Borel chromatic numbers
• Representation of invariant measures
• On the existence of a finite invariant measure
• A determinacy approach to Borel combinatorics
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS

Cited In (5)

• Title not available (Why is that?)
• Approximate Schreier decorations and approximate Kőnig's line coloring theorem
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Mathematical Foundations of Computer Science 2004
• Equivariant maps to subshifts whose points have small stabilizers

This page was built for publication: Equitable colourings of Borel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5014071)