The Locating-Chromatic number of an $n$-ary Trees

Abstract

The locating-chromatic number of a graph $G$ is the smallest integer $n$, such that $G$ has a proper $n$-coloring $c$ and all vertices have different vectors of distances to the colors generated by $c$. We study the asymptotic value of the locating-chromatic number of a $k$-level $n$-ary tree. The locating-chromatic number of this tree acts very differently when $k$ goes to infinity and when $n$ goes to infinity. If we fix $k\ge 2$, almost all $n$-ary Tree $T(n,k)$ satisfy ${\chi }_L(T(n,k))=n+k-1$; so $\underset{n\to \infty }{\lim }{\chi }_L(T(n,k))-n=k-1$. But if we fix $n\ge 2$, then ${\chi }_L(T(n,k))=o(k)$.