On (k, ℓ)-locating colorings of graphs

Abstract

Let c : V (G) → {1, . . . , ℓ} = [ℓ] be a proper vertex coloring of G and C(i) = {u ∈ V (G): c(u) = i} for i ∈ [ℓ]. The k-color code rk(v|c) of vertex v  is the ordered ℓ-tuple (aG(v, C(1)), . . . , aG(v, C(ℓ))) where aG(v, C(i)) = min{k, min{dG(v, x) : x ∈ C(i)}}. If every two vertices have different  color codes, then c is a (k, ℓ)-locating coloring of G. The k-locating chromatic number of graph G, denoted by χLk (G), is the smallest integer ℓ such that G has a (k, ℓ)-locating coloring. In this paper, we propose this concept as an extension of diam(G)-locating chromatic  number and 2-locating chromatic number which are known as the locating chromatic number, denoted χL(G), and neighbor-locating  chromatic number, denoted χLN (G), respectively. In this paper, we give sharp bounds for χLk (G ◦ H) and χL(G ⋄ H) where G ◦ H and G ⋄ H are the corona and edge corona of G and H, respectively. We formulate an integer linear programming model to determine χL2 (G),  noting that almost all graphs have diameter 2 and χLk (G) = χL2 (G) for every graph G of diameter 2.