دوستعلی مژده

Let $G=(V,E)$ be a simple graph. Any partition of $V(G)$ to $k$ independent subsets is called a $k$-coloring of $G$. If $\Pi=\{S_1,S_2,\cdots,S_k\}$ is a minimum such partition, then $k$ is a chromatic number of $G$, denoted by $\chi(G)=k$. A $k$-coloring $\Pi=\{S_1,S_2,\cdots, S_k\}$ is said to be a (metric-)locating coloring, (an ML-coloring), if for every pair of distinct vertices $u, v$, with same color, there exists a color class $S_j$ such that $d(u, S_j) \ne d(v, S_j)$. Minimum $k$ for $ML$-coloring of a graph $G$, is called (metric-)locating chromatic number $\chi_{L}(G)$ of $G$. A $k$-neighbor locating coloring of $G$ is a partition of $V(G)$ to $\Pi=\{S_1,S_2,\cdots, S_k\}$ such that for two vertices $u,v \in S_i$, there is a color class $S_j$ for which, one of them has a neighbor in $S_j$ and the other not. The minimum $k$ with this property, is said to be neighbor-locating chromatic number of $G$, denoted by $\chi_{NL}(G)$ of $G$. We initiate to continue the study of neighbor locating coloring of graphs which has been already by others authors. In \cite{alcon1} the authors posed three conjectures and we study these conjectures. We show that, for each pair $h, k$ of integers with $3 \le h \le k$, there exists a connected graph $G$ such that $\chi_L(G) =h$ and $\chi_{NL}(G) =k$, which proves the first conjecture. If $G$ and $H$ are connected graphs, then $\chi_{NL}(G[H]) \le \chi_{NL}(G \square H)$, that disproves the second conjecture. Finally, we investigate for a family of graphs $G$, $\chi_{NL}(\mu (G)) = \chi_{NL}(G) +1$, where $\mu (G)$ is the Mycielski graph of $G$, that proves the third conjecture for some families of graphs.