A note on local antimagic chromatic number of lexicographic product graphs

Gee-Choon Lau, Wai-Chee Shiu, K. Premalatha, Ruixue Zhang, M. Nalliah

Published 2022-08-31Version 1

Let $G = (V,E)$ be a connected simple graph. A bijection $f: E \rightarrow \{1,2,\ldots,|E|\}$ is called a local antimagic labeling of $G$ if $f^+(u) \neq f^+(v)$ holds for any two adjacent vertices $u$ and $v$, where $f^+(u) = \sum_{e\in E(u)} f(e)$ and $E(u$) is the set of edges incident to $u$. A graph $G$ is called local antimagic if $G$ admits at least a local antimagic labeling. The local antimagic chromatic number, denoted $\chi_{la}(G)$, is the minimum number of induced colors taken over local antimagic labelings of $G$. Let $G$ and $H$ be two disjoint graphs. The graph $G[H]$ is obtained by the lexicographic product of $G$ and $H$. In this paper, we obtain sufficient conditions for $\chi_{la}(G[H])\leq \chi_{la}(G)\chi_{la}(H)$. Consequently, we give examples of $G$ and $H$ such that $\chi_{la}(G[H]) = \chi(G)\chi(H)$, where $\chi(G)$ is the chromatic number of $G$. We conjecture that (i) there are infinitely many graphs $G$ and $H$ such that $\chi_{la}(G[H])=\chi_{la}(G)\chi_{la}(H) = \chi(G)\chi(H)$, and (ii) for $k\ge 1$, $\chi_{la}(G[H]) = \chi(G)\chi(H)$ if and only if $\chi(G)\chi(H) = 2\chi(H) + \lceil\frac{\chi(H)}{k}\rceil$, where $2k+1$ is the length of a shortest odd cycle in $G$.