Characterizing all trees with locating-chromatic number 3 - Edy Tri Baskoro; A Asmiati (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2013)
Let c be a proper k-coloring of a connected graph G. Let Π = {S_1, S_2,…, S_k} be the induced partition of V(G) by c, where S_i is the partition class having all vertices with color i.The color code c_Π(v) of vertex v is the orderedk-tuple (d(v,S_1), d(v,S_2),…, d(v,S_k)), whered(v,S_i)= min{d(v,x)|x S_i}, for 1≤ i≤ k.If all vertices of G have distinct color codes, then c iscalled a locating-coloring of G.The locating-chromatic number of G, denoted by χ_L(G), isthe smallest k such that G posses a locating k-coloring. Clearly, any graph of order n ≥ 2 have locating-chromatic number k, where 2 ≤ k ≤ n. Characterizing all graphswith a certain locating-chromatic number is a difficult problem. Up to now, we have known allgraphs of order n with locating chromatic number 2, n-1, or n.In this paper, we characterize all trees whose locating-chromatic number 3. We also give a family of trees with locating-chromatic number 4.