The Locating Chromatic Number of the Join of Graphs

Abstract

Let $f$ be a proper $k$-coloring of a connected graph $G$ and $\Pi =(V_1,V_2,...,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 }}(v):=(d(v,V_1),d(v,V_2),...,d(v,V_k)),$ where $d(v,V_i)=\min \{d(v,x)|x\in V_i\},1\le i\le k$. If distinct vertices have distinct color codes, then $f$ 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 the join of graphs. We show that when $G_1$ and $G_2$ are two connected graphs with diameter at most two, then $\Cchi_{{}_L}(G_1+G_2)=\Cchi_{{}_L}(G_1)+\Cchi_{{}_L}(G_2)$, where $G_1+G_2$ is the join of $G_1$ and $G_2$. Also, we determine the locating chromatic numbers of the join of paths, cycles and complete multipartite graphs.

Cited by in corpus (1)

• On locating and neighbor-locating colorings of sparse graphs