On the Locating Chromatic Number of the Cartesian Product of Graphs

Abstract

Let \(c\) be a proper \(k\)-coloring of a connected graph \(G\) and \(\Pi = (V_1, V_2, \ldots, V_k)\) be an ordered partition of \(V(G)\) into the resulting color classes. For a vertex \(v\) of \(G\), the color code of \(v\) with respect to \(\Pi\) is defined to be the ordered \(k\)-tuple \(c_\Pi := (d(v, V_1), d(v, V_2), \ldots, d(v, V_k))\), where \(d(v, V_i) = \min\{d(v, x) \mid x \in V_i\}\) for \(1 \leq i \leq k\). If distinct vertices have distinct color codes, then \(c\) is called a locating coloring. The minimum number of colors needed in a locating coloring of \(G\) is the locating chromatic number of \(G\), denoted by \(\chi_L(G)\). In this paper, we study the locating chromatic numbers of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.