One-dependent colorings of the star graph


Abstract in English

This paper is concerned with symmetric $1$-dependent colorings of the $d$-ray star graph $mathscr{S}^d$ for each $d ge 2$. We compute the critical point of the $1$-dependent hard-core processes on $mathscr{S}^d$, which gives a lower bound for the number of colors needed for a $1$-dependent coloring of $mathscr{S}^d$. We provide an explicit construction of a $1$-dependent $q$-coloring for any $q ge 5$ of the infinite subgraph $mathscr{S}^3_{(1,1,infty)}$, which is symmetric in the colors and whose restriction to any copy of $mathbb{Z}$ is some symmetric $1$-dependent $q$-coloring of $mathbb{Z}$. We also prove that there is no such coloring of $mathscr{S}^3_{(1,1,infty)}$ with $q = 4$ colors. A list of open problems are presented.

Download