%0 Journal Article
%T A bound for the locating chromatic number of trees
%J Transactions on Combinatorics
%I University of Isfahan
%Z 2251-8657
%A Behtoei, Ali
%A Anbarloei, Mahdi
%D 2015
%\ 03/01/2015
%V 4
%N 1
%P 31-41
%! A bound for the locating chromatic number of trees
%K Locating coloring
%K Locating chromatic number
%K tree
%K maximum degree
%R 10.22108/toc.2015.6024
%X Let $f$ be a proper $k$-coloring of a connected graph $G$ and $Pi=(V_1,V_2,ldots,V_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$, the color code of $v$ with respect to $Pi$ is defined to be the ordered $k$-tuple $c_{{}_Pi}(v)=(d(v,V_1),d(v,V_2),ldots,d(v,V_k)),$ where $d(v,V_i)=min{d(v,x):~xin V_i}, 1leq ileq k$. If distinct vertices have distinct color codes, then $f$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by $chi_{L}(G)$. In this paper, we study the locating chromatic numbers of trees. We provide a counter example to a theorem of Gary Chartrand et al. [G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl., 36 (2002) 89-101] about the locating chromatic number of trees. Also, we offer a new bound for the locating chromatic number of trees. Then, by constructing a special family of trees, we show that this bound is best possible.
%U https://toc.ui.ac.ir/article_6024_1de06593073b82da914fe9c02657202d.pdf