Equitable colourings of Borel graphs
Equitable colourings of Borel graphs
复制标题
Borel 图的公平着色
DOI：
10.1017/fmp.2021.12
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Conley, Clinton T.
中科院分区：
文献类型：
--
作者：
Bernshteyn, Anton;Conley, Clinton T.
Hajna和Szemerédi证明了：如果G是一个有最大度的有限图，则对每个整数，G都有一个k色的真染色，其中每两个色类的大小至多相差1，这样的染色被称为平均染色。在Borel集下，我们得到了无限图的类似结果。具体地说，如果G是有限最大度的非周期Borel图，则对每个图，G都有一个Borel真k-染色，其中每两个色类都由G的Borel满半群的一个元素联系在一起。我们还建立了Kostochka和Nakprset关于平均度小的图的均匀着色的一个结果的一个可测版本。也就是说，如果G在顶点上不含团，且是一个无原子的G-不变概率度量，使得G关于的平均次数至多为，则G有-均匀染色。作为这一结果的证明步骤，我们建立了由于Kostochka和Nakprite而加强的Brooks定理的可测和列表着色扩张。
Hajnal and Szemerédi proved that if G is a finite graph with maximum degree , then for every integer , G has a proper colouring with k colours in which every two colour classes differ in size at most by ; 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 , then for each , 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 -colourings of graphs with small average degree. Namely, we prove that if , G does not contain a clique on vertices and is an atomless G-invariant probability measure such that the average degree of G with respect to is at most , then G has a -equitable -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.
登录
查看更多内容
可测量颜色的布鲁克斯定理
DOI：
--
发表时间：
2016
期刊：
Forum of Mathematics, Sigma
影响因子：
--
作者：
Clinton T. Conley;Andrew S. Marks;Robin D. Tucker
通讯作者：
Robin D. Tucker
DOI：
10.1007/978-4-431-55108-9_1
发表时间：
2014
期刊：
--
影响因子：
--
作者：
S. Eigen;A. Hajian;Yuji Ito;V. Prasad
通讯作者：
S. Eigen;A. Hajian;Yuji Ito;V. Prasad
DOI：
10.1016/j.tcs.2005.09.031
发表时间：
2005-12
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
A. Kostochka;Kittikorn Nakprasit
通讯作者：
A. Kostochka;Kittikorn Nakprasit
可数Borel等价关系的分解与测度
影响因子：
0.9
作者：
Ruiyuan Chen
通讯作者：
Ruiyuan Chen
DOI：
--
发表时间：
2005
期刊：
--
影响因子：
--
作者：
A. V. Kostochkaa;K. Nakprasita
通讯作者：
A. V. Kostochkaa;K. Nakprasita