2024 : 6 : 21
Doost Ali Mojdeh

Doost Ali Mojdeh

Academic rank: Professor
ORCID:
Education: PhD.
ScopusId:
Faculty: Faculty of Mathematical Sciences
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Phone: 011-35302448

Research

Title
On the conjectures of neighbor locating coloring of graphs
Type
JournalPaper
Keywords
Coloring, Neighbor locating, Conjectures, Neighbor locating coloring
Year
2022
Journal THEORETICAL COMPUTER SCIENCE
DOI
Researchers Doost Ali Mojdeh

Abstract

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.