Approaches Which Output Infinitely Many Graphs With Small Local Antimagic Chromatic Number

Abstract

An edge labeling of a connected graph $G=(V,E)$ is said to be local antimagic if it is a bijection $f:E\to \{1,\dots ,|E|\}$ such that for any pair of adjacent vertices $x$ and $y$, $f^{+}(x)\ne f^{+}(y)$, where the induced vertex label $f^{+}(x)=\sum f(e)$, with $e$ ranging over all the edges incident to $x$. The local antimagic chromatic number of $G$, denoted by ${\chi }_{la}(G)$, is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$. In this paper, we (i) give a sufficient condition for a graph with one pendant to have ${\chi }_{la}\ge 3$. A necessary and sufficient condition for a graph to have ${\chi }_{la}=2$ is then obtained; (ii) give a sufficient condition for every circulant graph of even order to have ${\chi }_{la}=3$; (iii) construct infinitely many bipartite and tripartite graphs with ${\chi }_{la}=3$ by transformation of cycles; (iv) apply transformation of cycles to obtain infinitely many one-point union of regular (possibly circulant) or bi-regular graphs with ${\chi }_{la}=2,3$. The work of this paper suggests many open problems on the local antimagic chromatic number of bipartite and tripartite graphs.

A work that produces infinitely many bipartite graphs with local antimagic chromatic number is 2 or 3, and infinitely many tripartite graphs with local antimagic chromatic number is 3. Many open problems on bipartite and tripartite graphs are suggested