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 =(C_1,C_2,...,C_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 }}(v):=(d(v,C_1),d(v,C_2),...,d(v,C_k)),$ where $d(v,C_i)=\min \{d(v,x)|x\in C_i\},1\le i\le 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 $\Cchi_{{}_L}(G)$. In this paper, we study the locating chromatic number of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.

To appear in Ars Combinatorics

References in corpus (1)

• On the locating chromatic number of Kneser graphs