THE LOCATING-CHROMATIC NUMBER OF TREES AND CHARACTERIZATION OF TREES HAVING LARGE LOCATING-CHROMATIC NUMBER - KASTIKA SYOFYAN (NIM: 30113009), DIAN
The investigation on the locating chromatic number of graphs was firstly studied by Chartrand et.al on 2002 and now it has received much development. The concept of the locating chromatic number of graphs is a special case of the partition dimension of graphs. The locating-chromatic number of a graph G is defined as the cardinality of a minimum resolving partition of the vertex set V(G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices in G must not be contained in the same partition class. In this case, the coordinate of a vertex is expressed in terms of the distances of the vertex to all partition classes. The locating-chromatic numbers for some classes of graphs have been studied. However, the results are still very limited. One class of graphs which has received much attention in studying its locating-chromatic number is trees. However, up to now the results are still very limited and still far from satisfactory. As one of the important classes, trees have received much studies for various graph notions and concepts. The study of the locating-chromatic numbers for trees is still limited only to its subclasses such as paths, stars, double stars, amalgamation of stars, firecrackers, caterpillars, banana trees, n-ary trees, and lobsters. Therefore, in this dissertation, we examine the locating-chromatic number of some other classes of trees. The classes of trees studied in this dissertation are all trees having maximum degree 3 or 4, i.e. the trees that can be embedded in two-dimensional grid and binary trees. We show that the upper bound on the locating-chromatic number of trees embedded in two-dimensional grid is 5. Furthermore, we derive the upper bound on the locating chromatic number of binary trees depending on the diameter of such trees. This dissertation also discusses the locating-chromatic number of trees that are obtained by a graph operation. The graph operations investigated are the corona product and the edge-amalgamation on trees. The upper and lower bounds on the locating-chromatic number of trees obtained by these operations are derived. The decision problem for the locating chromatic number of any graph is an NPcomplete problem. This means that there is no efficient algorithm to determine the locating-chromatic number of any graph. Furuya and Matsumoto on 2015 have constructed a locating coloring algorithm to estimate an upper bound on the locating-chromatic number of trees. This upper bound depends on the number of leaves and the number of local end-branch in trees. In this dissertation, we propose a different algorithm to estimate the upper bound. The upper bound, which is generated from this algorithm, depends on diameter, maximum degree, and maximum number of end-path in trees. In this dissertation we also show the upper bound is better than the upper bound of Furuya dan Matsumoto. The characterisations of all graphs having a certain locating chromatic number have also been done. Chartrand et.al on 2002 characterized all graphs of order n with locating chromatic number n; namely they are complete multipartite graphs. Furthermore, Chartrand and Zhang on 2003 also characterized all graphs of order n with locating chromatic number n􀀀1. All graphs with locating chromatic number 3 are determined by Asmiati and Baskoro on 2012 and 2013. In this dissertation, we characterize all trees of order n with locating-chromatic number n􀀀t, for t < n=2.