LOCATING-CHROMATIC NUMBER OF TREES ANDCHARACTERIZATION OF GRAPHS WITH THELOCATING-CHROMATIC NUMBER 3
Asmiati Asmiati · 2012
The locating-chromatic number of a graph was introduced by Chartrand et al. in 2002. This concept is derived from the graph partition dimension and graph coloring. The partition dimension of a graph was firstly studied by Chartrand, Zhang, and Salehi in 1998. They gave the partition dimension for some classes of trees, such as paths, double stars, and caterpillars. Since then, many studies have been conducted to find the partition dimension for the other certain classes of graphs. For instances, Tomescu et al. (2007) showed the upper and lower bounds of the partition dimension of wheels, Javaid and Shokat (2008) determined the partition dimension of gear graph, helm, sunflower, and friendships graph. Let G = (V,E) be a connected graph and c be a proper k-coloring of G with colors 1, 2, . . . , k. Let � = {C1,C2, · · · ,Ck} be a partition of V (G), which is induced by coloring c. The color code c�(v) of v is the ordered k-tuple (d(v,C1), d(v,C2), . . . , d(v,Ck)) where d(v,Ci) = min{d(v, x)|x 2 Ci} for any i. If all distinct vertices of G have distinct color codes, then c is called a k-locating coloring of G. The locating-chromatic number, denoted by �L(G) is the smallest k such that G has a locating k-coloring. Chartrand et al. (2002) determined the locating-chromatic numbers of some well-known graph classes such as paths, cycles, complete multipartite graphs and double stars. Moreover, the locating-chromatic numbers for some particular trees are also considered by Chartrand et al. (2003a). They showed that for every integer t 2 [3, n] and t 6= n−1, there exists a tree of order n � 5 having locating-chromatic number t. However, determining the locating-chromatic numbers of all trees is still an open problem. In this dissertation, we determine the locating-chromatic number of some classes of trees, namely an amalgamation of stars, banana trees, firecrackers, and caterpillars. Chartrand et al. (2003a) characterized all graphs on n vertices with locatingchromatic number n, n−1, or n−2. In this dissertation, we characterize all graphs having locating-chromatic number 3. We also give all such edge maximal graphs (in terms of the number of edges) with locating-chromatic number 3. Keywords: color code, locating-chromatic number.