Factor of iid colorings of trees

2024/02/04 by Thornton, Riley
#03E15 (primary) #05C15 #60K35 (secondary) #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Probability (math.PR)

paper · doi:10.48550/arxiv.2402.02575

Abstract

We show that, for every ε>0, the 4-regular tree has an fiid 4-coloring where a given vertex is assigned the 4th color with probability at most ε. We also construct 5-colorings of T₆ improving known bounds on the measurable and approximate chromatic number of F₃.

Related

• One-dependent coloring by finitary factors
• Notes on Tree- and Path-chromatic Number
• Finitely dependent random colorings of bounded degree graphs
• An explicit edge-coloring of K_n with six colors on every K₅
• On the chromatic number of random d-regular graphs