Equitable colourings of Borel graphs
Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $\Delta $ , then for every integer $k \geq \Delta +1$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $1$ ; such colourings are called equitable. We obt...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2021-01-01
|
| Series: | Forum of Mathematics, Pi |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050508621000123/type/journal_article |
| _version_ | 1811156228815978496 |
|---|---|
| author | Anton Bernshteyn Clinton T. Conley |
| author_facet | Anton Bernshteyn Clinton T. Conley |
| author_sort | Anton Bernshteyn |
| collection | DOAJ |
| description | Hajnal and Szemerédi proved that if G is a finite graph with maximum degree
$\Delta $
, then for every integer
$k \geq \Delta +1$
, G has a proper colouring with k colours in which every two colour classes differ in size at most by
$1$
; such colourings are called equitable. We obtain an analogue 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 \geq \Delta + 1$
, G has a Borel proper k-colouring in which every two colour classes are related by an element of the Borel full semigroup of G. In particular, such colourings 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 $
-colourings of graphs with small average degree. Namely, we prove that if
$\Delta \geq 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 $
-colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit. |
| first_indexed | 2024-04-10T04:48:06Z |
| format | Article |
| id | doaj.art-4706ffbe755c4067b047c9f3a42482b6 |
| institution | Directory Open Access Journal |
| issn | 2050-5086 |
| language | English |
| last_indexed | 2024-04-10T04:48:06Z |
| publishDate | 2021-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Pi |
| spelling | doaj.art-4706ffbe755c4067b047c9f3a42482b62023-03-09T12:34:29ZengCambridge University PressForum of Mathematics, Pi2050-50862021-01-01910.1017/fmp.2021.12Equitable colourings of Borel graphsAnton Bernshteyn0https://orcid.org/0000-0001-8070-3408Clinton T. Conley1School of Mathematics, Georgia Institute of Technology, 686 Cherry St NW, Atlanta, GA 30332, USA.Department of Mathematical Sciences, Carnegie Mellon University, Wean Hall 6113, Pittsburgh, PA 15213, USA; E-mail: .Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $\Delta $ , then for every integer $k \geq \Delta +1$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $1$ ; such colourings are called equitable. We obtain an analogue 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 \geq \Delta + 1$ , G has a Borel proper k-colouring in which every two colour classes are related by an element of the Borel full semigroup of G. In particular, such colourings 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 $ -colourings of graphs with small average degree. Namely, we prove that if $\Delta \geq 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 $ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.https://www.cambridge.org/core/product/identifier/S2050508621000123/type/journal_articleequitable colouringBorel graphdescriptive combinatorics35P1505C15 |
| spellingShingle | Anton Bernshteyn Clinton T. Conley Equitable colourings of Borel graphs Forum of Mathematics, Pi equitable colouring Borel graph descriptive combinatorics 35P15 05C15 |
| title | Equitable colourings of Borel graphs |
| title_full | Equitable colourings of Borel graphs |
| title_fullStr | Equitable colourings of Borel graphs |
| title_full_unstemmed | Equitable colourings of Borel graphs |
| title_short | Equitable colourings of Borel graphs |
| title_sort | equitable colourings of borel graphs |
| topic | equitable colouring Borel graph descriptive combinatorics 35P15 05C15 |
| url | https://www.cambridge.org/core/product/identifier/S2050508621000123/type/journal_article |
| work_keys_str_mv | AT antonbernshteyn equitablecolouringsofborelgraphs AT clintontconley equitablecolouringsofborelgraphs |