TY - JOUR
ID - 6024
TI - A bound for the locating chromatic number of trees
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Behtoei, Ali
AU - Anbarloei, Mahdi
AD - Imam Khomeini International University
Y1 - 2015
PY - 2015
VL - 4
IS - 1
SP - 31
EP - 41
KW - Locating coloring
KW - Locating chromatic number
KW - tree
KW - maximum degree
DO - 10.22108/toc.2015.6024
N2 - 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):~x\in V_i\}, 1\leq i\leq 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.
UR - https://toc.ui.ac.ir/article_6024.html
L1 - https://toc.ui.ac.ir/article_6024_1de06593073b82da914fe9c02657202d.pdf
ER -