BROOKS’ THEOREM FOR MEASURABLE COLORINGS
BROOKS’ THEOREM FOR MEASURABLE COLORINGS
复制标题
可测量颜色的布鲁克斯定理
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Robin D. Tucker
中科院分区：
文献类型：
--
作者：
Clinton T. Conley;Andrew S. Marks;Robin D. Tucker
我们推广了布鲁克斯定理，证明了如果$G$是标准Borel空间$X$上的一个Borel图，其度以$ dgeqslant3 $为界，且不包含$(d+1)$ -团，则$G$对于$X$上的任意Borel概率测度${itmu}$具有可测的$d -着色，并且对于$X$上的任意兼容波兰拓扑具有可测的$ Baire $d -着色。该定理的证明使用了一种构造Borel图的单端生成子森林的新技术，以及来自列表着色研究的思想。将此定理应用于群作用产生的图，得到了d次Cayley图的IID - d -着色因子，除了两种例外情况。
We generalize Brooks’ theorem to show that if $G$ is a Borel graph on a standard Borel space $X$ of degree bounded by $dgeqslant 3$ which contains no $(d+1)$ -cliques, then $G$ admits a ${itmu}$ -measurable $d$ -coloring with respect to any Borel probability measure ${itmu}$ on $X$ , and a Baire measurable $d$ -coloring with respect to any compatible Polish topology on $X$ . The proof of this theorem uses a new technique for constructing one-ended spanning subforests of Borel graphs, as well as ideas from the study of list colorings. We apply the theorem to graphs arising from group actions to obtain factor of IID $d$ -colorings of Cayley graphs of degree $d$ , except in two exceptional cases.