Quaestiones Mathematicae, ( ISI ), Year (2024-7)

Title : ( On ( k , ℓ )-locating colorings of graphs )

Authors: Michael A. Henning , Mostafa Tavakoli ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote

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$‎.

Keywords

, $(k, \\\\\\\\ell)$-locating coloring‎, ‎locating coloring‎, ‎neighbor-locating coloring‎, ‎corona product‎, ‎edge corona product‎, ‎ILP model‎.