Locating-chromatic number of the edge-amalgamation of trees

Abstract

The investigation on the locating-chromatic number for graphs was initially studied by Chartrand et al. on 2002. This concept is in fact a special case of the partition dimension for graphs. Even though this topic has received much attention, the current progress is still far from satisfaction. We can define the locating-chromatic number of a graph G as the smallest integer k such that there exists a proper k-coloring on the vertex-set of G such that all vertices have distinct coordinates (color codes) with respect to this coloring. Not like the metric dimension of any tree which is completely solved, the locating-chromatic number for most types of trees are still open. In this paper, we study the locating-chromatic number of trees. In particular, we give lower and upper bounds of the locating-chromatic number of trees formed by an edge-amalgamation of the collection of smaller trees. We also show that the bounds are tight.