Equitable colourings of Borel graphs

DOI10.1017/FMP.2021.12MaRDI QIDQ5014071zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn, Clinton T. Conley

Publication date 6 December 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Borel measureequitable coloring

Mathematics Subject Classification ID

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

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.

Recommendations

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• On equitable -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

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 976831 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• scientific article; zbMATH DE number 3062900 (Why is no real title available?)
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• A determinacy approach to Borel combinatorics
• A fast algorithm for equitable coloring
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS
• Borel chromatic numbers
• Equitable coloring and the maximum degree
• Groups of Automorphisms of Borel Spaces
• On equitable -coloring of graphs with low average degree
• On the existence of a finite invariant measure
• Representation of invariant measures
• The Structure of Hyperfinite Borel Equivalence Relations
• Topics in orbit equivalence

Cited in

(6)

• scientific article; zbMATH DE number 6452992 (Why is no real title available?)
• 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
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS

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)