The locating-chromatic number for Halin graphs

Document Type : Original paper


1 Institut Teknologi Bandung

2 Technical University in Koˇsice


Let G be a connected graph. Let f be a proper k -coloring of G and Π = (R_1, R_2, . . . , R_k) be
an ordered partition of V (G) into color classes. For any vertex v of G, define the color code c_Π(v) of v with respect to Π to be a k -tuple (d(v, R_1), d(v, R_2), . . . , d(v, R_k)), where d(v, R_i) is the min{d(v, x)|x ∈ R_i}. If distinct vertices have distinct color codes, then we call f a locating coloring
of G. The locating-chromatic number of G, denoted by χL(G), is the least number k such that G
admits a locating coloring with k colors. In this paper, we determine the locating-chromatic number
of Halin graphs. We also give the locating-chromatic number of Halin graphs of double stars.


Main Subjects