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.
A. H. Assiyatun and E. T. Baskoro (2011). Locating-chromatic number of amalgamation of stars. ITB J. Sci.. 43A, 1-8 A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs. to appear in Ars
Combin.. A. Behtoei and B. Omoomi (2011). On the locating chromatic number of Kneser graphs. Discrete Appl. Math.. 159, 2214-2221 G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater and P. Zhang (2002). The locating-chromatic number of a graph. Bull. Inst. Combin. Appl.. 36, 89-101 G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater and P. Zhang (2003). Graphs of order n with locating-chromatic
number n − 1. Discrete Math.. 269 (13), 65-79 G. Chartrand, F. Okamoto and P. Zhang (2009). The metric chromatic number of a graph. Australas. J. Combin.. 44, 273-286 G. Chartrand, V. Saenpholphat and P. Zhang (2005). Resolving edge colorings in graphs. Ars Combin.. 74, 33-47 G. Chartrand, E. Salehi and P. Zhang (2000). The partition dimension of a graph,. Aequationes Math.. 59 (1-2), 45-54 F. Harary and R. A. Melter (1976). On the metric dimension of a graph. Ars Combinatoria. 2, 191-195 V. Saenpholphat and P. Zhang Conditional resolvability in graphs: A survey. 2004 (37-40), 1997-2017
Behtoei, A., & Anbarloei, M. (2015). A bound for the locating chromatic number of trees. Transactions on Combinatorics, 4(1), 31-41. doi: 10.22108/toc.2015.6024
MLA
Ali Behtoei; Mahdi Anbarloei. "A bound for the locating chromatic number of trees". Transactions on Combinatorics, 4, 1, 2015, 31-41. doi: 10.22108/toc.2015.6024
HARVARD
Behtoei, A., Anbarloei, M. (2015). 'A bound for the locating chromatic number of trees', Transactions on Combinatorics, 4(1), pp. 31-41. doi: 10.22108/toc.2015.6024
VANCOUVER
Behtoei, A., Anbarloei, M. A bound for the locating chromatic number of trees. Transactions on Combinatorics, 2015; 4(1): 31-41. doi: 10.22108/toc.2015.6024
)
