Locating-chromatic number of the edge-amalgamation of trees

Hilda Assiyatun, Dian Kastika Syofyan, Edy Tri Baskoro


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.


locating-chromatic number; tree; edge-amalgamation

Full Text:


DOI: http://dx.doi.org/10.19184/ijc.2020.4.2.6


Asmiati, H. Assiyatun, and E.T. Baskoro, Locating-chromatic number of amalgamation of stars, ITB J. Sci. 43 A (1) (2011), 1–8.

Asmiati, E.T. Baskoro, H. Assiyatun, D. Suprijanto, R. Simanjuntak, and S. Uttunggadewa, The locating-chromatic number of firecracker graphs, Far East J. Math. Sci. 63:1 (2012), 11–23.

Asmiati, Bilangan kromatik lokasi graf pohon dan karakterisasi graf dengan bilangan kromatik lokasi 3, Disertasi Program Studi Doktor Matematika, Institut Teknologi Bandung, 2012 (in Indonesian).

E.T. Baskoro and Asmiati, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1 (2) (2013), 109–117.

G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002), 89–101.

D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, On the locating-chromatic number of homogeneous lobster, AKCE Int. J. Graphs Comb. 10 (3) (2013), 245–252.

D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, The locating-chromatic number of binary trees, Elsevier, The 2nd International Conference of Graph Theory and Information Security, 74 (2015), 79–83.

D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, Trees with certain locating-chromatic number, J. Math. Fund. Sci. 48 (1) (2016), 39–47.

D. Welyyanti, E.T. Baskoro, R. Simanjuntak, and S. Uttunggadewa, On locating-chromatic number of complete n-ary tree, AKCE Int. J. Graphs Combin. 3 (2013), 309–315.


  • There are currently no refbacks.

ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats