One-dependent colorings of the star graph

Abstract: This paper is concerned with symmetric

1

-dependent colorings of the

d

-ray star graph

m a t h s c r S^{d}

for

d g e 2

. We compute the critical point of the

1

-dependent hard-core processes on

m a t h s c r S^{d}

, which gives a lower bound for the number of colors needed for a

1

-dependent coloring of

m a t h s c r S^{d}

. We provide an explicit construction of a

1

-dependent

q

-coloring for any

q g e 5

of the infinite subgraph

m a t h s c r S_{(1, 1, i n f t y)}^{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

m a t h s c r S_{(1, 1, i n f t y)}^{3}

with

q = 4

colors. A list of open problems are presented.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: One-dependent colorings of the star graph