Title : ( On ( k , ℓ )-locating colorings of graphs )
Authors: Michael A. Henning , Mostafa Tavakoli ,Access to full-text not allowed by authors
Abstract
Let $c \\\\\\\\colon V(G) \\\\\\\\rightarrow \\\\\\\\{1,\\\\\\\\ldots,\\\\\\\\ell\\\\\\\\} = [\\\\\\\\ell]$ be a proper vertex coloring of $G$ and $C(i) = \\\\\\\\{u\\\\\\\\in V(G) \\\\\\\\colon \\\\\\\\ c(u) = i \\\\\\\\}$ for $i\\\\\\\\in [\\\\\\\\ell]$. The $k$-color code $r_k(v|c)$ of vertex $v$ is the ordered $\\\\\\\\ell$-tuple $(a_G(v,C(1)),\\\\\\\\ldots,a_G(v,C(\\\\\\\\ell)))$ where $a_G(v,C(i))=\\\\\\\\min\\\\\\\\{k, \\\\\\\\min\\\\\\\\{d_G(v,x) \\\\\\\\, \\\\\\\\colon \\\\\\\\, x\\\\\\\\in C(i)\\\\\\\\}\\\\\\\\}$. If every two vertices have different color codes, then $c$ is a $(k,\\\\\\\\ell)$-locating coloring of $G$. The $k$-locating chromatic number of graph $G$, denoted by $\\\\\\\\chi_{L_k}(G)$, is the smallest integer $\\\\\\\\ell$ such that $G$ has a $(k,\\\\\\\\ell)$-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 $\\\\\\\\chi_L(G)$, and neighbor-locating chromatic number, denoted $\\\\\\\\chi_{LN}(G)$, respectively. In this paper, we give sharp bounds for $\\\\\\\\chi_{L_k}(G\\\\\\\\circ H)$ and $\\\\\\\\chi_L(G\\\\\\\\diamond H)$ where $G \\\\\\\\circ H$ and $G\\\\\\\\diamond H$ are the corona and edge corona of $G$ and $H$, respectively. We formulate an integer linear programming model to determine $\\\\\\\\chi_{L_2}(G)$, noting that almost all graphs have diameter~$2$ and $\\\\\\\\chi_{L_k}(G)=\\\\\\\\chi_{L_2}(G)$ for every graph $G$ of diameter~$2$.