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

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

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

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

A bound for the locating chromatic number of trees

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

2

A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs. to appear in Ars
Combin..

3

A. Behtoei and B. Omoomi (2011). On the locating chromatic number of Kneser graphs. Discrete Appl. Math.. 159, 2214-2221

4

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

5

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

6

G. Chartrand, F. Okamoto and P. Zhang (2009). The metric chromatic number of a graph. Australas. J. Combin.. 44, 273-286

7

G. Chartrand, V. Saenpholphat and P. Zhang (2005). Resolving edge colorings in graphs. Ars Combin.. 74, 33-47

8

G. Chartrand, E. Salehi and P. Zhang (2000). The partition dimension of a graph,. Aequationes Math.. 59 (1-2), 45-54

9

F. Harary and R. A. Melter (1976). On the metric dimension of a graph. Ars Combinatoria. 2, 191-195

10

V. Saenpholphat and P. Zhang Conditional resolvability in graphs: A survey. 2004 (37-40), 1997-2017