One-dependent colorings of the star graph

Abstract

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

24 pages, 2 figures, 2 tables. Minor revisions

References in corpus (1)

• Finitely dependent cycle coloring