Journal of the
Korean Mathematical Society JKMS

We study colorings of regular trees using subball complexity $b(n)$, which is the number of colored $n$-balls up to color-preserving isomorphisms. We show that for any $k$-regular tree, for $k>1$, there are colorings of intermediate complexity. We then construct colorings of linear complexity $b(n)=2n+2$. We also construct colorings induced from sequences of linear subword complexity which has exponential subball complexity.

Keywords: trees, colorings of trees, subword complexity, symbolic dynamics, Sturmian sequences, Sturmian colorings

MSC numbers: Primary 37B10, 37E25, 05C05