On Bridge Graphs with Local Antimagic Chromatic Number 3

Abstract

Let $G=(V,E)$ be a connected graph. A bijection $f:E\to \{1,\dots ,|E\left|\right\}$ is called a local antimagic labeling if, for any two adjacent vertices x and y, $f^{+}\left(x\right)\ne f^{+}\left(y\right)$, where $f^{+}\left(x\right)={\sum }_{e\in E\left(x\right)}f\left(e\right)$, and $E\left(x\right)$ is the set of edges incident to x. Thus, a local antimagic labeling induces a proper vertex coloring of G, where the vertex x is assigned the color $f^{+}\left(x\right)$. The local antimagic chromatic number ${\chi }_{la}\left(G\right)$ is the minimum number of colors taken over all colorings induced by local antimagic labelings of G. In this paper, we present some families of bridge graphs with ${\chi }_{la}\left(G\right)=3$ and give several ways to construct bridge graphs with ${\chi }_{la}\left(G\right)=3$.

1. Introduction

For a connected graph $G=(V,E)$ with order $\left|V\right|$ and size $\left|E\right|$, a local antimagic labeling is a bijection $f:E\to \{1,\dots ,|E\left|\right\}$ such that $f^{+}\left(u\right)\ne f^{+}\left(v\right)$ whenever the vertices u and v are adjacent in G, where $f^{+}\left(u\right)$ is the sum of the labels of the edges incident to u. Thus, a local antimagic edge labeling f of G induces a vertex labeling $f^{+}:V\to \mathbb{Z}$ given by $f^{+}\left(u\right)={\sum }_{u\in e\in E}f\left(e\right)$ for any two adjacent vertices with distinct labels. This vertex labeling is called an induced vertex labeling, and the labels assigned to vertices are called induced colors under f (or colors, for short, if no ambiguity occurs). A connected graph G is said to be local antimagic if it admits a local antimagic edge labeling. Clearly, if G is local antimagic, then $\left|V\right(G\left)\right|\ge 3$. The color number of a local antimagic labeling f is the number of distinct induced colors under f, denoted by $c\left(f\right)$, and f is also called a local antimagic $c\left(f\right)$-coloring. The local antimagic chromatic number of a graph G, denoted by ${\chi }_{la}\left(G\right)$, is the minimum $c\left(f\right)$ over all local antimagic labelings f of G. Thus, $2\le {\chi }_{la}\left(G\right)\le \left|V\left(G\right)\right|$.

The concept of local antimagic labeling was first introduced by Arumugam et al. [1] in 2017, marking the beginning of extensive research into local antimagic chromatic numbers of various graph classes. Building on this foundation, Nazula et al. [2] investigated unicyclic graphs in 2018, contributing to an early understanding of this parameter. Arumugam et al. [3] determined the local antimagic chromatic number of several families of trees. Subsequently, Lau et al. made significant advancements by determining the local antimagic chromatic numbers for several important graph families, including cycle-related join graphs [4], complete bipartite graphs [5], and spider graphs [6]. Further expanding the scope, Shaebani [7] constructed an infinite class of connected graphs with arbitrarily large local antimagic chromatic numbers. Recently, Lau et al. characterized s-bridge graphs with local antimagic chromatic number 2 in [8]. A bridge graph (or specifically, an s-bridge graph), denoted by $\theta (a_1,a_2,\dots ,a_s)$, is a graph consisting of s edge-disjoint $(u,v)$-paths of lengths $a_1,a_2,\dots ,a_s$, where $s\ge 2$. Up to isomorphic, we often assume $1\le a_1\le a_2\le \cdots \le a_s$, but not always. Figure 1 shows an s-bridge graph $\theta (2,2,4,4)$ with a local antimagic 3-coloring.

In this paper, we will further study s-bridge graphs ${\theta }_s$ and present some families of s-bridge graphs with local antimagic chromatic number 3.

Throughout this paper, we use $a^{\left[n\right]}$ to denote a sequence of length n in which all items are a, where $n\ge 2$. For integers $1\le a<b$, we let $[a,b]$ denote the set of integers from a to b. All notions and notation not defined in this paper are referred to in [9].

2. s-Bridge Graphs with Size 2s + 2

In this section, we will study a family of s-bridge graphs of size $2s+2$ and show that their local antimagic chromatic number is 3.

Firstly, we recall some known results regarding s-bridge graphs of sizes greater than $2s+2$.

Theorem 1

([8], Theorem 2.3). For $s\ge 3$, ${\chi }_{la}\left({\theta }_s\right)=2$ if and only if either ${\theta }_s=K_{2,s}$ with even $s\ge 4$ or ${\theta }_s$ is one of the following graphs of sizes greater than $2s+2$:

(1) 

$\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$, where $l\ge 1$;

(2) 

$\theta (2l-2,{(4l-2)}^{[3l-1]})$, where $l\ge 2$;

(3) 

$\theta (2,4^{\left[3\right]},6)$; $\theta (4,8^{\left[5\right]},{10}^{\left[2\right]})$; $\theta (6,{12}^{\left[7\right]},{14}^{\left[3\right]})$;

(4) 

$\theta (4l-2-2t,2t,{(4l-4)}^{\left[l\right]},{(4l-2)}^{[l-2]})$, where $2\le l\le t\le {\displaystyle \frac{5l-2}{4}}$;

(5) 

$\theta (4l-2-2t,2t-2,{(4l-4)}^{[l-1]},{(4l-2)}^{[l-1]})$, where $2\le l\le t\le {\displaystyle \frac{5l}{4}}$;

(6) 

$\theta (2t,4s-6-2t,2s-4,{(4s-6)}^{[s-3]})$, where ${\displaystyle \frac{2s-3}{8}}\le t\le {\displaystyle \frac{6s-5}{8}}$ and $s\ge 4$.

In the remainder of this section, we consider a family of s-bridge graphs ${\theta }_s$ that are bipartite and of size $2s+2$, where $s\ge 3$. Clearly, ${\theta }_s=\theta (2^{[s-1]},4)$. In [8], it has been proved that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\ge 3$. Next, we will show that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)=3$.

Theorem 2.

For any $s\ge 2$, ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)=3$.

Before proving Theorem 2, we introduce some notation that will be used later. Let A be a matrix. We use $r_i\left(A\right)$ and $c_j\left(A\right)$ to denote the i-th row sum and the j-th column sum of A, respectively. And, $J_{m,n}$ denotes an $m\times n$ matrix whose entries are 1.

Proof. 

As ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\ge 3$, it is sufficient to show that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\le 3$ holds for any $s\ge 2$. For any $1\le j\le s-1$, let $P_j=u{w}_{j}v$ be the j-th $(u,v)$-path in ${\theta }_s$ and $P_s=u{z}_1{z}_2{z}_{3}v$ be the s-th $(u,v)$-path in ${\theta }_s$. In each case below, we will define a matrix that corresponds to a local antimagic 3-coloring of $\theta (2^{[s-1]},4)$, which implies that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\le 3$.

Case 1. s is odd, and $s\ge 3$.

In this case, we have the following two cases.

Case 1.1. $s+1=4r\ge 4$ (i.e., $s\equiv 3(mod4)$).

We will define a $2\times 4r$ matrix recurrently such that the set of its entries is $[1,8r]$ for $r\ge 1$.

Let ${\Psi }_4=\left(\begin{array}{cccc}1& 7& 6& 3\\ 8& 2& 4& 5\end{array}\right)$. It is clear that (i) the set of entries of ${\Psi }_4$ is $[1,8]$, (ii) $c_1\left({\Psi }_4\right)=c_2\left({\Psi }_4\right)$, and (iii) $r_2\left({\Psi }_4\right)-r_1\left({\Psi }_4\right)=2$. Suppose that ${\Psi }_{4r}$ is a $2\times 4r$ matrix satisfying the following conditions: (i) the set of entries is $[1,8r]$; (ii) for any $1\le j_1,j_2\le 4r-2$, $c_{j_1}\left({\Psi }_{4r}\right)=c_{j_2}\left({\Psi }_{4r}\right)$; and (iii) $r_2\left({\Psi }_{4r}\right)-r_1\left({\Psi }_{4r}\right)=2$, where $r\ge 1$.

Let

$${\Psi }_{4r+4}=\left(\begin{array}{cccc}1& 8r+7& 8r+6& 4\\ 8r+8& 2& 3& 8r+5\end{array}|{\Psi }_{4r}+4J_{2,4r}\right).$$

Consequently, we have a $2\times (s+1)$ matrix ${\Psi }_{s+1}={\left({\psi }_{i,j}\right)}_{2\times (s+1)}$ satisfying the following conditions: (i) the set of entries is $[1,2s+2]$; (ii) for any $1\le j_1,j_2\le s-1$, $c_{j_1}\left({\Psi }_{s+1}\right)=c_{j_2}\left({\Psi }_{s+1}\right)$ (i.e., the sum of the entries in column 1 is the same as the sum of the entries in column 2); and (iii) $r_2\left({\Psi }_{s+1}\right)-r_1\left({\Psi }_{s+1}\right)=2$.

Clearly, $c_j\left({\Psi }_{s+1}\right)=2s+3$ for any $1\le j\le s-1$, $r_1\left({\Psi }_{s+1}\right)=R-1$ and $r_2\left({\Psi }_{s+1}\right)=R+1$, where $R={\displaystyle \frac{1}{2}}(s+1)(2s+3)$. Also, the last two columns of ${\Psi }_{s+1}$ form a matrix $\left(\begin{array}{cc}s+3& s\\ s+1& s+2\end{array}\right)$.

Now, we are ready to label the edges of ${\theta }_s$. Let f be an edge labeling of ${\theta }_s$ such that for any $1\le j\le s-1$, the edges $u{w}_j$ and $w_{j}v$ are assigned the labels ${\psi }_{1,j}$ and ${\psi }_{2,j}$, and the edges $u{z}_1$, $z_1{z}_2$, $z_2{z}_3$ and $z_{3}v$ are assigned the labels ${\psi }_{1,s}=s+3$, ${\psi }_{1,s+1}=s$, ${\psi }_{2,s+1}=s+2$ and ${\psi }_{2,s}=s+1$, respectively. We have that $f^{+}\left(w_j\right)=2s+3$ for each $1\le j\le s-1$, $f^{+}\left(z_1\right)=f^{+}\left(z_3\right)=2s+3$, $f^{+}\left(z_2\right)=2s+2$ and $f^{+}\left(u\right)=f^{+}\left(v\right)=R-(s+1)\ge 3s+5$. Thus, f is a local antimagic 3-coloring of $\theta (2^{[s-1]},4)$, which implies that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\le 3$.

Case 1.2. $s+1=4r+2\ge 6$ (i.e., $s\equiv 1(mod4)$).

Similar to Case 1.1, we will define a $2\times (4r+2)$ matrix recurrently such that the set of its entries is $[1,8r+4]$ for $r\ge 1$.

Let ${\Psi }_6=\left(\begin{array}{ccccc}1& 11& 9& 6& 8\\ 12& 2& 4& 7& 10\end{array}\begin{array}{c}5\\ 3\end{array}\right)$. It is obvious that for $1\le j_1,j_2\le 4$, $c_{j_1}\left({\Psi }_6\right)=c_{j_2}\left({\Psi }_6\right)=13$, and $r_1\left({\Psi }_6\right)-r_2\left({\Psi }_6\right)=2$. Suppose that ${\Psi }_{4r+2}$ is a $2\times (4r+2)$ matrix satisfying the following conditions: (i) the set of entries is $[1,8r+4]$; (ii) for any $1\le j_1,j_2\le 4r$, $c_{j_1}\left({\Psi }_{4r+2}\right)=c_{j_2}\left({\Psi }_{4r+2}\right)$; and (iii) $r_2\left({\Psi }_{4r+2}\right)-r_1\left({\Psi }_{4r+2}\right)=2$, where $r\ge 1$.

Let

$${\Psi }_{4r+6}=\left(\begin{array}{cccc}1& 8r+11& 8r+10& 4\\ 8r+12& 2& 3& 8r+9\end{array}|{\Psi }_{4r+2}+4J_{2,4r+2}\right).$$

Clearly, ${\Psi }_{s+1}={\left({\psi }_{i,j}\right)}_{2\times (s+1)}$ is a $2\times (s+1)$ matrix in which $c_j\left({\Psi }_{s+1}\right)=2s+3$ for each $1\le j\le s-1$ and $r_1\left({\Psi }_{s+1}\right)-r_2\left({\Psi }_{s+1}\right)=2$, where $r_1\left({\Psi }_{s+1}\right)={\displaystyle \frac{1}{2}}(2s^2+5s+5)$ and $r_2\left({\Psi }_{s+1}\right)={\displaystyle \frac{1}{2}}(2s^2+5s+1)$. Note that the last two columns of ${\Psi }_{s+1}$ are a matrix $\left(\begin{array}{cc}s+3& s\\ s+5& s-2\end{array}\right)$.

Let f be an edge labeling of ${\theta }_s$ such that the edges $u{w}_j$ and $w_{j}v$ are labeled by ${\psi }_{1,j}$ and ${\psi }_{2,j}$ for each $1\le j\le s-1$, and the edges $u{z}_1$, $z_1{z}_2$, $z_2{z}_3$ and $z_{3}v$ are labeled by ${\psi }_{1,s}=s+3$, ${\psi }_{1,s+1}=s$, ${\psi }_{2,s+1}=s-2$ and ${\psi }_{2,s}=s+5$, respectively. Then, $f^{+}\left(w_j\right)=2s+3$ for each $1\le j\le s-1$, $f^{+}\left(z_1\right)=f^{+}\left(z_3\right)=2s+3$, $f^{+}\left(z_2\right)=2s-2$, $f^{+}\left(u\right)=r_1\left({\Psi }_{s+1}\right)-s={\displaystyle \frac{1}{2}}(2s^2+3s+5)$ and $f^{+}\left(v\right)=r_2\left({\Psi }_{s+1}\right)-(s-2)={\displaystyle \frac{1}{2}}(2s^2+3s+5)\ge 5s+10$. Therefore, f is a local antimagic 3-coloring of $\theta (2^{[s-1]},4)$, implying ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\le 3$.

Case 2. s is even, and $s\ge 4$. There are also two subcases in this case.

Case 2.1. $s=4r\ge 4$ (i.e., $s\equiv 0(mod4)$).

Let ${\Lambda }_4=\left(\begin{array}{cc}{A}_4& D\end{array}\right)$, where $A_4=\left(\begin{array}{ccc}3& 7& 6\\ 8& 4& 5\end{array}\right)$ and $D=\left(\begin{array}{c}2\\ 1\end{array}\right)$. Note that the set of entries of ${\Lambda }_4$ is $[1,8]$, and $r_i\left({\Lambda }_4\right)=18$ for each $i\in \{1,2\}$. Suppose that ${\Lambda }_{4r}=\left(\begin{array}{cc}{A}_{4r}& D\end{array}\right)$ is defined so that the set of entries of ${\Lambda }_{4r}$ is $[1,8r]$, and $r_i\left({\Lambda }_{4r}\right)=2r(8r+1)$ for each $i\in \{1,2\}$, where $r\ge 1$. Let ${\Lambda }_{4(r+1)}=\left(\begin{array}{cc}{A}_{4(r+1)}& D\end{array}\right)$, where $A_{4(r+1)}=\left(\begin{array}{cc}{A}_{4r}+4J_{2,4r-1}& B_{4r}\end{array}\right)$ and $B_{4r}=\left(\begin{array}{cccc}3& 8r+7& 8r+6& 6\\ 8r+8& 4& 5& 8r+5\end{array}\right)$.

It is clear that the set of entries of ${\Lambda }_{4(r+1)}$ is $[1,8(r+1\left)\right]$, and for each $i\in \{1,2\}$,

$$\begin{array}{cc}\hfill r_i\left({\Lambda }_{4(r+1)}\right)& =r_i\left(A_{4(r+1)}\right)+r_i\left(D\right)=r_i\left(A_{4r}\right)+4(4r-1)+r_i\left(B_{4r}\right)+r_i\left(D\right)\hfill \\ \hfill & =r_i\left({\Lambda }_{4r}\right)+16r-4+(16r+22)=2r(8r+1)+32r+18\hfill \\ \hfill & =2(r+1)(8r+9).\hfill \end{array}$$

Thus, ${\Lambda }_{4n}$ is a $2\times 4n$ matrix with the entry set $[1,8n]$, where $n\ge 1$, the sum of the elements in each row is $2n(8n+1)$, the sum of the elements in each column except the last column is $8n+3$, and the last column is ${\left(\begin{array}{cc}2& 1\end{array}\right)}^T$.

Case 2.2. $s=4r+2\ge 6$ (i.e., $s\equiv 2(mod4)$).

Let ${\Lambda }_6=\left(\begin{array}{cc}{A}_6& D\end{array}\right)$, where $A_6=\left(\begin{array}{ccccc}12& 4& 5& 9& 7\\ 3& 11& 10& 6& 8\end{array}\right)$. Note that the set of entries of ${\Lambda }_6$ is $[1,12]$, and $r_i\left({\Lambda }_6\right)=39$ for each $i\in \{1,2\}$. Suppose that ${\Lambda }_{4r+2}=\left(\begin{array}{cc}{A}_{4r+2}& D\end{array}\right)$ is defined so that the set of entries of ${\Lambda }_{4r+2}$ is $[1,8r+4]$, and $r_i\left({\Lambda }_{4r+2}\right)=2r(8r+9)+5$ for each $i\in \{1,2\}$, where $r\ge 1$. Let ${\Lambda }_{4(r+1)+2}=\left(\begin{array}{cc}{A}_{4(r+1)+2}& D\end{array}\right)$, where $A_{4(r+1)+2}=\left(\begin{array}{cc}{A}_{4r+2}+4J_{2,4r+1}& B_{4r+2}\end{array}\right)$ and $B_{4r+2}=\left(\begin{array}{cccc}3& 8r+11& 8r+10& 6\\ 8r+12& 4& 5& 8r+9\end{array}\right)$.

It is obvious that the set of entries of ${\Lambda }_{4(r+1)+2}$ is $[1,8r+12]$, and the sum of the elements in each row is

$$\begin{array}{cc}\hfill r_i\left({\Lambda }_{4(r+1)+2}\right)& =r_i\left(A_{4(r+1)+2}\right)+r_i\left(D\right)=r_i\left(A_{4r+2}\right)+4(4r+1)+r_i\left(B_{4r+2}\right)+r_i\left(D\right)\hfill \\ \hfill & =r_i\left({\Lambda }_{4r+2}\right)+16r+4+(16r+30)=[2r(8r+9)+5]+32r+34\hfill \\ & =2(r+1)(8r+17)+5.\hfill \end{array}$$

Therefore, ${\Lambda }_{4n+2}$ is a $2\times 4n+2$ matrix with the entry set $[1,8n+4]$, where $n\ge 1$, the sum of the elements in each row is $2n(8n+9)+5$, the sum of the elements in each column except the last column is $8n+7$, and the last column is ${\left(\begin{array}{cc}2& 1\end{array}\right)}^T$.

Combining Case 2.1 and Case 2.2, when s is even and $s\ge 4$, we always obtain a $2\times s$ matrix ${\Lambda }_s={\left({\lambda }_{i,j}\right)}_{2\times s}$, in which the set of entries is $[1,2s]$, $r_i\left({\Lambda }_s\right)={\displaystyle \frac{s(2s+1)}{2}}$ for each $i\in \{1,2\}$, and $c_j\left({\Lambda }_s\right)=2s+3$ for each $1\le j\le s-1$.

For any even integer $s\ge 4$, let f be an edge labeling of $\theta (2^{[s-1]},4)$ such that $f\left(u{w}_j\right)={\lambda }_{1,j}$ and $f\left(w_{j}v\right)={\lambda }_{2,j}$ for each $1\le j\le s-1$, $f\left(u{z}_1\right)={\lambda }_{1,s}=2$, $f\left(z_1{z}_2\right)=2s+1$, $f\left(z_2{z}_3\right)=2s+2$ and $f\left(z_{3}v\right)={\lambda }_{2,s}=1$. Then, we have that $f^{+}\left(z_1\right)=f^{+}\left(z_3\right)=2s+3$, $f^{+}\left(z_2\right)=4s+3$, $f^{+}\left(u\right)=f^{+}\left(v\right)={\displaystyle \frac{s(2s+1)}{2}}=s^2+{\displaystyle \frac{s}{2}}\ge 6s+3$, and $f^{+}\left(w_j\right)=2s+3$ for each $1\le j\le s-1$. Therefore, f is a local antimagic 3-coloring, implying that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)\le 3$.

From Case 1 and Case 2, we have that ${\chi }_{la}\left(\theta (2^{[s-1]},4)\right)=3$ for any $s\ge 2$. □

Remark 1.

In Case 1.1, we obtain a local antimagic 3-coloring f of $\theta (2^{[s-1]},4)$ such that $f^{+}\left(u\right)=f^{+}\left(v\right)$. If we require $f^{+}\left(u\right)\ne f^{+}\left(v\right)$, then there is only one case, which is $s=5$. Following is the assignment of each $(u,v)$-path in $\theta (2^{\left[4\right]},4)$: $1,12;2,11;3,10;4,9;5,8,7,6$, which induce the vertex labels $13,15$ and 48.

3. Bridge Graphs with an Even Number of Internal Paths of the Same Length

In this section, we will show that there is a family of bridge graphs with an even number of internal paths of the same length whose local antimagic chromatic number is 3.

Theorem 3.

For positive integers $m_1,\cdots ,m_l$, ${\chi }_{la}\left(\theta (m_1^{\left[2\right]},\cdots ,m_l^{\left[2\right]})\right)\le 3$, where $l\ge 1$.

Note that $m_1,\cdots ,m_l$ in Theorem 3 do not necessarily have to be distinct or in non-decreasing order. Before giving the proof of Theorem 3, we first introduce some notions and results that will be used later.

For positive integer s and integers $i,d$, let $A_s(i;d)$ be the arithmetic progression of length s with a first term i and a common difference d. Suppose that $A_1$ and $A_2$ are two ordered sequences of length n. Let $A_1\diamond A_2$ be the ordered sequence of length $2n$ generated by $A_1$ and $A_2$ such that the $(2i-1)$-st term is the i-th term of $A_1$ and the $\left(2i\right)$-th term is the i-th term of $A_2$, where $1\le i\le n$. When the length of $A_1$ is $n+1$, we may similarly define $A_1\diamond A_2$ as an ordered sequence of length $2n+1$.

The following result can be obtained easily.

Lemma 1.

For $m,q\in \mathbb{N}$ and $a,b\in \mathbb{Z}$, let $I_{m,q}\left(a\right)=A_m(a;2)\diamond A_m(q-a;-2)$ and $D_{m,q}\left(b\right)=A_m(b;-2)\diamond A_m(q-b+2;2)$. Then,

(1) 

The first and last terms of $I_{m,q}\left(a\right)$ are a and $q-a-2m+2$;

(2) 

The sums of two consecutive terms of $I_{m,q}\left(a\right)$ are q and $q+2$, alternatingly;

(3) 

The first and last terms of $D_{m,q}\left(b\right)$ are b and $q-b+2m$;

(4) 

The sums of two consecutive terms of $D_{m,q}\left(b\right)$ are $q+2$ and q, alternatingly.

From Lemma 1, we obtain the following result immediately.

Corollary 1.

The sum of the first term of $I_{m,q}\left(a\right)$ and that of $D_{m,q}(q+1-a)$ is $q+1$, and the sum of the last term of $I_{m,q}\left(a\right)$ and that of $D_{m,q}(q+1-a)$ is also $q+1$.

Similar to Lemma 1 and Corollary 1, we have the following.

Lemma 2.

For $m,q\in \mathbb{N}$ and $a,b\in \mathbb{Z}$, let $I_{m,q}^{*}\left(a\right)=A_{m+1}(a;2)\diamond A_m(q-a;-2)$ and $D_{m,q}^{*}=A_{m+1}(b;-2)\diamond A_m(q-b+2;2)$. Then,

(1) 

The first and last terms of $I_{m,q}^{*}\left(a\right)$ are a and $a+2m$;

(2) 

The sums of two consecutive terms of $I_{m,q}^{*}\left(a\right)$ are q and $q+2$, alternatively;

(3) 

The first and last terms of $D_{m,q}^{*}\left(b\right)$ are b and $b-2m$;

(4) 

The sums of two consecutive terms of $D_{m,q}^{*}\left(b\right)$ are $q+2$ and q, alternatively;

(5) 

The sum of the first term of $I_{m,q}^{*}\left(a\right)$ and that of $D_{m,q}^{*}\left(b\right)$ is $a+b$, and the sum of the last term of $I_{m,q}^{*}\left(a\right)$ and that of $D_{m,q}^{*}\left(b\right)$ is also $a+b$.

Suppose that q is fixed. If there is no ambiguity, we will write $I_m\left(a\right)$, $D_m\left(b\right)$, $I_m^{*}\left(a\right)$ and $D_m^{*}\left(b\right)$ instead of $I_{m,q}\left(a\right)$, $D_{m,q}\left(b\right)$, $I_{m,q}^{*}\left(a\right)$ and $D_{m,q}^{*}\left(b\right)$, respectively. With some abuse of notation, we sometimes treat the ordered sequence as a set.

Now, we are ready to prove Theorem 3.

Proof of Theorem 3.

Let $\theta =\theta (m_1^{\left[2\right]},\cdots ,m_l^{\left[2\right]})$. Without loss of generality, we may assume that $m_1,\cdots ,m_h$ are even and $m_{h+1},\cdots ,m_l$ are odd, $0\le h\le l$. Note that if $h=0$, then there is no even-length $(u,v)$-path, and if $h=l$, then there is no odd-length $(u,v)$-path. For any $1\le i\le 2h$, let $R_i$ be a $(u,v)$-path of length $m_i=2r_i$ in $\theta$, and for any $2h+1\le i\le 2l$, let $Q_i$ be a $(u,v)$-path of length $m_i=2r_i+1$ in $\theta$. Then, the size of $\theta$ is $q=2{\displaystyle \sum _{i=1}^{2l}}{r}_i+2(l-h)$. Without loss of generality, we assume $r_1\le \cdots \le r_{2h}$ and $r_{2h+1}\le \cdots \le r_{2l}$. Thus, by assumption, $r_{2j-1}=r_{2j}$ for $1\le j\le l$.

Now, we label the edges of the $(u,v)$-paths of $\theta$ according to the following eight steps:

Step 1.

If $h=0$, then jump to Step 5.

Step 2.

Label the edges of $(u,v)$-path $R_1$ by $I_{r_1}\left(1\right)$ and the edges of $(u,v)$-path $R_2$ by $D_{r_2}\left(q\right)$.

Step 3.

Suppose that for each $j\ge 1$, $R_{2j}$ has been labeled. Let $a_j$ be the least unused label. Observe that, by definition, $a_j=1+{\displaystyle \sum _{i=1}^{2j}}{r}_i$. Label the edges of $(u,v)$-path $R_{2j+1}$ by $I_{r_{2j+1}}\left(a_j\right)$ and the edges of $(u,v)$-path $R_{2j+2}$ by $D_{r_{2j+2}}(q-a_j+1)$.

Step 4.

Repeat Step 3 until all $R_i$ are labeled.

Step 5.

If $h=l$, then stop; otherwise, let $b_0$ be the least unused label. Observe that, by definition, $b_0=1+{\displaystyle \sum _{i=1}^{2h}}{r}_i$. Empty summation is treated as 0.

Step 6.

Label the edges of $(u,v)$-path $Q_{2h+1}$ by $I_{r_{2h+1}}^{*}\left(b_0\right)$ and the edges of $(u,v)$-path $Q_{2h+2}$ by $D_{r_{2h+2}}^{*}(q-b_0+1)$.

Step 7.

Suppose that $Q_{2h+2j}$ has been labeled for each $j\ge 1$. Let $b_j$ be the least unused label. Observe that, by definition, $b_j=j+1+{\displaystyle \sum _{i=1}^{2h+2j}}{r}_i$. Label the edges of $(u,v)$-path $Q_{2h+2j+1}$ by $I_{r_{2h+2j+1}}^{*}\left(b_j\right)$ and the edges of $(u,v)$-path $Q_{2h+2j+2}$ by $D_{r_{2h+2j+2}}^{*}(q-b_j+1)$.

Step 8.

Repeat Step 7 until every $Q_i$ is labeled.

Note that $r_{2j+1}=r_{2j+2}$. For $j\ge 0$, we have a set

$$\begin{array}{cc}& I_{r_{2j+1}}\left(a_j\right)\cup D_{r_{2j+2}}(q-a_j+1)\hfill \\ & =A_{r_{2j+1}}(a_j,2)\cup A_{r_{2j+1}}(q-a_j;-2)\cup A_{r_{2j+2}}(q-a_j+1;-2)\cup A_{r_{2j+2}}(a_j+1;2)\hfill \\ \hfill & =[a_j,a_j+2r_{2j+1}-1]\cup [q-a_j-2r_{2j+1}+2,q-a_j+1]\hfill \\ \hfill & =[a_j,a_j+r_{2j+1}+r_{2j+2}-1]\cup [q-a_j-r_{2j+1}-r_{2j+2}+2,q-a_j+1]\hfill \\ \hfill & =\left[1+\sum _{i=1}^{2j}{r}_i,\sum _{i=1}^{2j+2}{r}_i\right]\cup \left[q+1-\sum _{i=1}^{2j+2}{r}_i,q-\sum _{i=1}^{2j}{r}_i\right],\hfill \end{array}$$

where $a_0=1$. Similarly, for $1\le j\le l-h$, we have that

$$\begin{array}{cc}& I_{r_{2h+2j-1}}^{*}\left(b_{j-1}\right)\cup D_{r_{2h+2j}}^{*}(q-b_{j-1}+1)\hfill \\ \hfill & =\left[j+\sum _{i=1}^{2h+2j-2}{r}_i,j+\sum _{i=1}^{2h+2j}{r}_i\right]\cup \left[q+1-j-\sum _{i=1}^{2h+2j}{r}_i,q+1-j-\sum _{i=1}^{2h+2j-2}{r}_i\right].\hfill \end{array}$$

Since $q=2{\displaystyle \sum _{i=1}^{2l}}{r}_i+2(l-h)$, all labels in $[1,q]$ are assigned. By Lemmas 1 and 2 and Corollary 1, we can check that the induced vertex labels are q, $q+2$ and $l(q+1)$. Thus, the above labeling is a local antimagic 3-coloring of $\theta$, implying that ${\chi }_{la}\left(\theta \right)\le 3$. □

Combining Theorems 1 and 3, we easily obtain the following result.

Theorem 4.

For integers $2\le m_1\le \cdots \le m_l$, $l\ge 1$, if $\theta (m_1^{\left[2\right]},\cdots ,m_l^{\left[2\right]})$ is not in the list of Theorem 1, then ${\chi }_{la}\left(\theta (m_1^{\left[2\right]},\cdots ,m_l^{\left[2\right]})\right)=3$.

Following are three examples of Theorem 4.

Example 1.

According to the notation used in the proof of Theorem 3, we have a local antimagic 3-coloring for $\theta (2^{\left[2\right]},4^{\left[2\right]})$, as shown in Figure 1.

Example 2.

Consider the graph $\theta (2^{\left[2\right]},4^{\left[2\right]},6^{\left[4\right]},{10}^{\left[2\right]})$. According to the notation used in the proof of Theorem 3, $h=l=5$, $q=56$, $r_1=r_2=1$, $r_3=r_4=2$, $r_5=r_6=r_7=r_8=3$ and $r_9=r_{10}=5$. We label $R_i$, $1\le i\le 10$, as follows:

Label $R_1$ by $I_1\left(1\right)=1,55$ (we will omit the braces of the sequences in each example);

Label $R_2$ by $D_1\left(56\right)=56,2$;

Label $R_3$ by $I_2\left(3\right)=3,53,5,51$;

Label $R_4$ by $D_2\left(54\right)=54,4,52,6$;

Label $R_5$ by $I_3\left(7\right)=7,49,9,47,11,45$;

Label $R_6$ by $D_3\left(50\right)=50,8,48,10,46,12$;

Label $R_7$ by $I_3\left(13\right)=13,43,15,41,17,39$;

Label $R_8$ by $D_3\left(44\right)=44,14,42,16,40,18$;

Label $R_9$ by $I_5\left(19\right)=19,37,21,35,23,33,25,31,27,29$;

Label $R_{10}$ by $D_5\left(38\right)=38,20,36,22,34,24,32,26,30,28$.

One may see that the induced vertex labels are 56, 58 and 285. From Theorem 1, we know that ${\chi }_{la}\left(\theta (2^{\left[2\right]},4^{\left[2\right]},6^{\left[4\right]},{10}^{\left[2\right]})\right)\ne 2$. Thus, ${\chi }_{la}\left(\theta (2^{\left[2\right]},4^{\left[2\right]},6^{\left[4\right]},{10}^{\left[2\right]})\right)=3$.

Example 3.

Consider the graph $\theta (2^{\left[2\right]},4^{\left[2\right]},6^{\left[4\right]},7^{\left[2\right]})$. According to the notation used in the proof of Theorem 3, $l=5$, $h=4$, $q=50$, $r_1=r_2=1$, $r_3=r_4=2$, $r_5=r_6=r_7=r_8=3$ and $r_9=r_{10}=3$. We label $R_i$ for $1\le i\le 8$ and $Q_i$ for $i=9,10$ as follows:

Label $R_1$ by $I_1\left(1\right)=1,49$;

Label $R_2$ by $D_1\left(50\right)=50,2$;

Label $R_3$ by $I_2\left(3\right)=3,47,5,45$;

Label $R_4$ by $D_2\left(48\right)=48,4,46,6$;

Label $R_5$ by $I_3\left(7\right)=7,43,9,41,11,39$;

Label $R_6$ by $D_3\left(44\right)=44,8,42,10,40,12$;

Label $R_7$ by $I_3\left(13\right)=13,37,15,35,17,33$;

Label $R_8$ by $D_3\left(38\right)=38,14,36,16,34,18$;

Label $Q_9$ by $I_3^{*}\left(19\right)=19,31,21,29,23,27,25$;

Label $Q_{10}$ by $D_3^{*}\left(32\right)=32,20,30,22,28,24,26$.

One may see that the induced vertex labels are 50, 52 and 255. Since $\theta (2^{\left[2\right]},4^{\left[2\right]},6^{\left[4\right]},7^{\left[2\right]})$ is not bipartite, ${\chi }_{la}\left(\theta (2^{\left[2\right]},4^{\left[2\right]},6^{\left[4\right]},7^{\left[2\right]})\right)=3$.

4. Construct Some Bridge Graphs with Local Antimagic 3-Coloring

In the last section of this paper, we will give several ways to construct some bridge graphs such that their local antimagic chromatic number is 3.

4.1. From Bridge Graphs with Local Antimagic 2-Coloring

From Theorem 1(1), there is a local antimagic 2-coloring of $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$, where $l\ge 1$ (see the proof of Theorem 2.3 in [8] for more details). In what follows, we will give a local antimagic 3-coloring of $\theta (4l^{[3l+2]},{(4l+1)}^{\left[l\right]})$ based on the local antimagic 2-coloring of $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$.

For a bridge graph $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$, let $Q_j$ be the $(u,v)$-path of length $4l$, where $1\le j\le 3l+2$, and $R_i$ be the $(u,v)$-path of length $4l+2$, where $1\le i\le l$. Let f be a local antimagic 2-coloring of $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$ obtained by the method described by [8] (Theorem 2.3). We see that the first three edge labels of $R_i$ starting from u are $i,x-i,y-x+i$, where $x=q+1$, $y-x=8l+4$, and q is the size of $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$.

Now, we perform the following steps to create a local antimagic 3-coloring of $\theta (4l^{[3l+2]},{(4l+1)}^{\left[l\right]})$:

• Delete the edge labeled by $x-i$ from $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$ for each $1\le i\le l$ (i.e., the second edge of $R_i$);
• Merge two pendent vertices incident to the edges labeled by i and $y-x+l-i+1$ as a new vertex $w_i$ for each $1\le i\le l$.

We now obtain the new graph $\theta (4l^{[3l+2]},{(4l+1)}^{\left[l\right]})$, in which the induced vertex label of $w_i$ is $y-x+l+1=9l+5$, and the induced vertex labels of other vertices are the same as those in $\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$, which are $x=16l^2+10l+1$ and $y=16l^2+18l+5$. As $\theta (4l^{[3l+2]},{(4l+1)}^{\left[l\right]})$ is not in the list of Theorem 1 (since every bridge graph in the list only has paths of even length), we have the following result.

Theorem 5.

For $l\ge 1$, ${\chi }_{la}\left(\theta (4l^{[3l+2]},{(4l+1)}^{\left[l\right]})\right)=3$.

Example 4.

We will give a local antimagic 3-coloring of the bridge graph $\theta (8^{\left[8\right]},9^{\left[2\right]})$ in the following. Firstly, we consider the bridge graph $\theta (8^{\left[8\right]},{10}^{\left[2\right]})$. Let $R_1,R_2$ be the $(u,v)$-paths of length 10 and $Q_i$ be the $(u,v)$-path of length 8, where $1\le i\le 8$. From the proof of Theorem 2.3 in [8]), we label as follows:

Label $R_1$ by 1, 84, 21, 64, 41, 44, 61, 24, 81, 4;

Label $R_2$ by 2, 83, 22, 63, 42, 43, 62, 23, 82, 3;

Label $Q_1$ by 7, 78, 27, 58, 47, 28, 67, 18;

Label $Q_2$ by 8, 77, 28, 57, 48, 37, 68, 17;

Label $Q_3$ by 9, 76, 29, 56, 49, 36, 69, 16;

Label $Q_4$ by 11, 74, 31, 54, 51, 34, 71, 14;

Label $Q_5$ by 13, 72, 33, 52, 53, 32, 73, 12;

Label $Q_6$ by 15, 70, 35, 50, 55, 30, 75, 10;

Label $Q_7$ by 19, 66, 39, 46, 59, 26, 79, 6;

Label $Q_8$ by 20, 65, 40, 45, 60, 25, 80, 5.

We obtain $\theta (8^{\left[8\right]},9^{\left[2\right]})$ by deleting the edges labeled by 83 and 84 in $\theta (8^{\left[8\right]},{10}^{\left[2\right]})$, merging the pendent vertices incident to the edges labeled by 1 and 83 and merging the pendent vertices incident to the edges labeled by 2 and 84. Thus, the new paths of length 9 in $\theta (8^{\left[8\right]},9^{\left[2\right]})$ are labeled by $2,21,64,41,44,61,24,81,4$ and $1,22,63,42,43,62,23,82,3$. The labels of other paths of length 8 are the same as those in $\theta (8^{\left[8\right]},{10}^{\left[2\right]})$. It is clear that the induced colors are $85,105 and 23$. Therefore, this is a local antimagic 3-coloring for $\theta (8^{\left[8\right]},9^{\left[2\right]})$.

4.2. From Some Special Sequences

In what follows, we will construct some bridge graphs of sizes $4m+3$ and $4m$, where $m\ge 1$, from some special sequences and show that their local antimagic chromatic number is 3.

Let $A_{2m+2}(4m+3;-1)$ and $A_{2m+1}(1;1)$ be two arithmetic progressions, where $m\ge 1$. We break the sequence $A_{2m+2}(4m+3;-1)\diamond A_{2m+1}(1;1)$ into three subsequences of lengths $2m+1$, $2k-1$ and $2m-2k+3$ as follows:

$$\begin{array}{cc}\hfill S_1& =A_{m+1}(4m+3;-1)\diamond A_m(1;1)=(4m+3,1,4m+2,2,\cdots ,m,3m+3);\hfill \\ \hfill S_2& =A_k(m+1;1)\diamond A_{k-1}(3m+2;-1)=(m+1,3m+2,\cdots ,3m-k+4,m+k),\hfill \\ \hfill S_3^{*}& =A_{m-k+2}(3m-k+3;-1)\diamond A_{m-k+1}(m+k+1;1)\hfill \\ & =(3m-k+3,m+k+1,\cdots ,2m+1,2m+2),\hfill \end{array}$$

where $1\le k\le m$. Note that $S_2=\{m+1\}$ when $k=1$. Let $S_3$ be the reverse of $S_3^{*}$, i.e., $S_3=(2m+2,2m+1,\cdots ,m+k+1,3m-k+3)$. Observe that the set of elements in $S_1$ is $[1,m]\cup [3m+3,4m+3]$, the set of elements in $S_2$ is $[m+1,m+k]\cup [3m-k+4,3m+2]$, and the set of elements in $S_3$ is $[m+k+1,2m+1]\cup [2m+2,3m-k+3]$. Thus, all the elements in $[1,4m+3]$ appear exactly once.

Clearly, the sum of two consecutive terms of $S_i$ for each $1\le i\le 3$ is either $q+1$ or q. The sum of the first terms of $S_1$, $S_2$ and $S_3$ is $(4m+3)+(m+1)+(2m+2)=7m+6$, and that of the last terms of $S_1$, $S_2$ and $S_3$ is $(3m+3)+(m+k)+(3m-k+3)=7m+6$.

Now, we label the edges of three $(u,v)$-paths of lengths $2m+1$, $2k-1$ and $2m-2k+3$ by the sequences $S_1$, $S_2$ and $S_3$, respectively. Therefore, there is a local antimagic 3-coloring of $\theta =\theta (2m+1,2k-1,2m-2k+3)$ for each $1\le k\le m$. Since $\theta$ is not in the list of Theorem 1, we have the following result.

Theorem 6.

For $1\le k\le m$, ${\chi }_{la}\left(\theta (2k-1,2m-2k+3,2m+1)\right)=3$.

Suppose that we break the above sequence $S_1$ into the following three subsequences of lengths $2l$, 2 and $2m-2l-1$, where $1\le l\le m-1$:

$$\begin{array}{cc}\hfill T_1& =A_l(4m+3;-1)\diamond A_l(1;1)=(4m+3,1,\cdots ,4m-l+4,l);\hfill \\ \hfill T_2& =(l+1,4m-l+3);\hfill \\ \hfill T_3& =A_{m-l}(4m-l+2;-1)\diamond A_{m-l-1}(l+2;1)=(4m-l+2,l+2,\cdots ,m,3m+3).\hfill \end{array}$$

We label the edges of five $(u,v)$-paths of lengths $2l$, 2, $2m-2l-1$, $2k-1$ and $2m-2k+3$ by the sequences $T_1$, $T_2$, $T_3$, $S_2$ and $S_3$, respectively. Then, there is a local antimagic 3-coloring for $\theta =\theta (2,2l,2m-2l-1,2k-1,2m-2k+3)$ when $1\le k\le m$ and $1\le l\le m-1$. Also, as $\theta$ is not in the list of Theorem 1, we obtain the following result.

Theorem 7.

For $1\le k\le m$ and $1\le l\le m-1$, ${\chi }_{la}\left(\theta (2,2l,2m-2l-1,2k-1,2m-2k+3)\right)=3$.

Example 5.

Suppose $m=3$ and $k=2$. We then have that

$$\begin{array}{cc}\hfill S_1& =15,1,14,2,13,3,12;\hfill \\ \hfill S_2& =4,11,5;\hfill \\ \hfill S_3& =8,7,9,6,10.\hfill \end{array}$$

Thus, we label the $(u,v)$-paths of lengths $7,3,5$ by $S_1,S_2,S_3$, respectively. We then obtain a local antimagic 3-coloring of $\theta (3,5,7)$ with induced colors $15,16,27$, implying that ${\chi }_{la}\left(\theta (3,5,7)\right)=3$.

Now, we break $S_1$ into $T_1=15,1$, $T_2=2,14$ and $T_3=13,3,12$. Then, the $(u,v)$-paths of lengths $2,2,3,3,5$ are labeled by $T_1,T_2,T_3,S_2,S_3$, respectively. Therefore, there is a local antimagic 3-coloring for $\theta (2,2,3,3,5)$ with induced colors $15,16,42$. Thus, ${\chi }_{la}\left(\theta (2,2,3,3,5)\right)=3$.

In what follows, we will construct the bridge graph of size $4m$, where $m\ge 1$, from the sequences $A_m(4m;-1)$, $A_m(1;1)$, $A_m(2m;-1)$ and $A_m(2m+1;1)$. Let

$$\begin{array}{cc}\hfill S_1& =A_m(4m;-1)\diamond A_m(1;1)=\{4m,1,\cdots ,3m+1,m\};\hfill \\ \hfill S_2& =A_m(2m;-1)\diamond A_m(2m+1;1)=\{2m,2m+1,\cdots ,m+1,3m\}.\hfill \end{array}$$

Note that the sums of two consecutive terms of $S_1$ (or $S_2$) are $4m+1$ and $4m$, alternatingly.

We break $S_1$ into $2h$ subsequences with even lengths, i.e.,

$$\begin{array}{cc}\hfill S_1^1& =(4m,1,\cdots ,4m+1-x_1,x_1);\hfill \\ \hfill S_1^2& =(4m-x_1,x_1+1,\cdots ,4m+1-x_2,x_2);\hfill \\ \hfill ⋮& ⋮\hfill \\ \hfill S_1^{2h-1}& =(4m-x_{2h-2},x_{2h-2}+1,\cdots ,4m+1-x_{2h-1},x_{2h-1});\hfill \\ \hfill S_1^{2h}& =(4m-x_{2h-1},x_{2h-1}+1,\cdots ,4m+1-x_{2h},x_{2h})\hfill \end{array}$$

Note that $x_{2h}=m$, which is the last term of $S_1$. That is, for each $1\le i\le 2h$,

$$S_1^i=(4m-x_{i-1},x_{i-1}+1,\cdots ,4m+1-x_i,x_i),$$

where $x_0=0$ by convention. The length of $S_1^i$ is $2a_i=2(x_i-x_{i-1})$ for $1\le i\le 2h$.

Similarly, we break $S_2$ into $2k+1$ subsequences with even lengths; i.e., for each $1\le j\le 2k+1$,

$$S_2^j=(4m-y_{j-1},y_{j-1}+1,\cdots ,4m+1-y_j,y_j),$$

where $y_0=2m$ by convention. Note that $y_{2k+1}=3m$, and the length of $S_2^j$ is $2b_j=2(y_j-y_{j-1})$ for $1\le j\le 2k+1$.

The sums of two consecutive terms of $S_1^i$ (or $S_2^j$) are still $4m+1$ and $4m$, alternatingly. Now, we reverse the order of the sequence of each $S_1^{2l}$ and keep the order of the sequence $S_1^{2l-1}$ for $1\le l\le h$. We also reverse the order of the sequence of each $S_2^{2l}$ for $1\le l\le k$ and keep the order of the sequence $S_2^{2l-1}$ for $1\le l\le k+1$. The new sequences are denoted by $T_1^i$ and $T_2^j$ accordingly.

The sum of all first terms of $T_1^i$ is $4mh+x_{2h}=4mh+m$, and that of all last terms of $T_1^i$ is $4mh$. Similarly, the sum of all first terms of $T_2^j$ is $4m(k+1)-y_0=4m(k+1)-2m$, and that of all last terms of $T_2^j$ is $4mk+y_{2k+1}=4mk+3m$. Thus, the sum of all first terms of $T_1^i$ and $T_2^j$ is

$$4mh+m+4m(k+1)-2m=4m(h+k)+3m,$$

and that of all last terms of $T_1^i$ and $T_2^j$ is

$$4mh+4mk+3m=4m(h+k)+3m.$$

We label the edges of $2(h+k)+1$$(u,v)$-paths of lengths $2a_1$, $2a_2$, ⋯, $2a_{2h}$, $2b_1$, $2b_2$, ⋯, $2b_{2k+1}$ by the sequences $T_1^1$, $T_1^2$, ⋯, $T_1^{2h}$, $T_2^1$, $T_2^2$, ⋯, $T_2^{2k+1}$, respectively. Then, the following result is obtained.

Theorem 8.

Let $\theta =\theta (2a_1,2a_2,\cdots ,2a_{2h},2b_1,2b_2,\cdots ,2b_{2k+1})$, where ${\displaystyle \sum _{i=1}^{2h}}{a}_i={\displaystyle \sum _{j=1}^{2k+1}}{b}_j$. Then, ${\chi }_{la}\left(\theta \right)=3$ if $\theta \notin \{\theta (2,4^{\left[3\right]},6),\theta (6,{12}^{\left[7\right]},{14}^{\left[3\right]}),\theta (2n,4n-2,6n-2,{(8n-2)}^{[n-2]})\}$, where $n\ge 2$.

Proof. 

Let $\theta =\theta (2a_1,2a_2,\cdots ,2a_{2h},2b_1,2b_2,\cdots ,2b_{2k+1})$. From the above discussion, ${\chi }_{la}\left(\theta \right)\le 3$.

If ${\chi }_{la}\left(\theta \right)=2$, then $\theta$ is one of the graphs listed in item $\left(2a\right)$ or 4 of Theorem 1, since the number of internal paths is odd.

(a)

Suppose $\theta =\theta (2l-2,{(4l-2)}^{[3l-1]})$, where $l\ge 2$. The size of $\theta$ is $(2l-2)+(3l-1)(4l-2)=4(3l^2-2l)$.

If $2l-2$ is one of $2a_i$, then all $2b_j$ are $4l-2$.

If $2l-2$ is one of $2b_j$, then all $2a_i$ are $4l-2$.

For each case, $y(2l-1)=3l^2-2l$ for some $y\in \mathbb{N}$. Thus, $y\equiv 0(modl)$. Let $y=kl$ for some $k\in \mathbb{N}$. Then, $k(2l-1)=3l-2$ or $(k-1)(2l-1)=l-1$, and there is no solution when $l\ge 2$.

(b)

Suppose $\theta =\theta (2t,4s-6-2t,2s-4,{(4s-6)}^{[s-3]})$, where ${\displaystyle \frac{2s-3}{8}}\le t\le {\displaystyle \frac{6s-5}{8}}$ and $s\ge 4$. Moreover, s is odd, say $s=2n+1\ge 5$. The size of $\theta$ is $4(s^2-3s+2)$. Then,

$$\begin{array}{cc}\hfill ta+(2s-3-t)b+(s-2)c+(2s-3)y& =s^2-3s+2\hfill \\ \hfill t(1-a)+(2s-3-t)(1-b)+(s-2)(1-c)+(2s-3)(s-3-y)& =s^2-3s+2\hfill \end{array}$$

for some $a,b,c\in \{0,1\}$ and $0\le y\le 2n-2$.

Suppose $a=b=c=0$ (it is the same case when $a=b=c=1$). Then,

$$y={\displaystyle \frac{{(2n+1)}^2-3(2n+1)+2}{2(2n+1)-3}}={\displaystyle \frac{4n^2-2n}{4n-1}}=n-{\displaystyle \frac{n}{4n-1}}\notin \mathbb{Z}.$$

Suppose $a=b=0$ and $c=1$ (it is the same case as when $a=b=1$ and $c=0$). Then,

$$y={\displaystyle \frac{{(2n+1)}^2-4(2n+1)+4}{2(2n+1)-3}}={\displaystyle \frac{4n^2-4n+1}{4n-1}}=n-1+{\displaystyle \frac{n}{4n-1}}\notin \mathbb{Z}.$$

Suppose $a=c=0$ and $b=1$ (it is the same case as when $a=c=1$ and $b=0$). Then,

$$y={\displaystyle \frac{{(2n+1)}^2-5(2n+1)+5+t}{4n-1}}={\displaystyle \frac{4n^2-6n+1+t}{4n-1}}=n-2+{\displaystyle \frac{3n-1+t}{4n-1}},$$

where ${\displaystyle \frac{4n-1}{8}}\le t\le {\displaystyle \frac{12n+1}{8}}$. Thus, ${\displaystyle \frac{3n-1+t}{4n-1}}\in \mathbb{N}$ and $0<{\displaystyle \frac{28n-9}{32n-8}}\le {\displaystyle \frac{3n-1+t}{4n-1}}\le {\displaystyle \frac{36n-7}{32n-8}}<2$, which implies that ${\displaystyle \frac{3n-1+t}{4n-1}}=1$, i.e., $t=n$. Therefore, $\theta =\theta (6n-2,{(8n-2)}^{[n-1]},2n,4n-2,{(8n-2)}^{[n-1]})=\theta (2n,4n-2,6n-2,{(8n-2)}^{[n-2]})$, which is excluded from the hypothesis.

Suppose $b=c=0$ and $a=1$ (it is the same case as when $b=c=1$ and $a=0$). Then,

$$y={\displaystyle \frac{{(2n+1)}^2-3(2n+1)+2-t}{4n-1}}={\displaystyle \frac{4n^2-2n-t}{4n-1}}=n-{\displaystyle \frac{n+t}{4n-1}},$$

where ${\displaystyle \frac{4n-1}{8}}\le t\le {\displaystyle \frac{12n+1}{8}}$. Thus, ${\displaystyle \frac{n+t}{4n-1}}\in \mathbb{N}$ and $0<{\displaystyle \frac{12n-1}{32n-8}}\le {\displaystyle \frac{n+t}{4n-1}}\le {\displaystyle \frac{20n+1}{32n-8}}<1$. There is no solution.

□

Example 6.

Suppose $m=6$. Then,

$$\begin{array}{cc}\hfill S_1& =24,1,23,2,22,3,21,4,20,5,19,6;\hfill \\ \hfill S_2& =18,7,17,8,16,9,15,10,14,11,13,12.\hfill \end{array}$$

If we choose $h=1$, $k=1$, $a_1=1$, $a_2=5$, $b_1=1$, $b_2=1$ and $b_3=4$, then we have

$$\begin{array}{cccc}\hfill T_1^1& =24,1;\hfill & \hfill T_2^1& =12,13;\hfill \\ \hfill T_1^2& =6,19,5,20,4,21,3,22,2,23;\hfill & \hfill T_2^2& =14,11;\hfill \\ & & \hfill T_2^3& =10,15,9,16,8,17,7,18.\hfill \end{array}$$

This is a local antimagic 3-coloring for $\theta (2,10,2,2,8)=\theta (2,2,2,8,10)$ with colors 24, 25, 66.

If we choose $h=1$, $k=3$, $a_1=3$, $a_2=3$, $b_1=1$, $b_2=1$, $b_3=2$, $b_4=1$ and $b_5=1$, then we have

$$\begin{array}{cccc}\hfill T_1^1& =24,1,23,2,22,3;\hfill & \hfill T_2^1& =12,13;\hfill \\ \hfill T_1^2& =6,19,5,20,4,21;\hfill & \hfill T_2^2& =14,11;\hfill \\ & & \hfill T_2^3& =10,15,9,16;\hfill \\ & & \hfill T_2^4& =17,8;\hfill \\ & & \hfill T_2^5& =7,18.\hfill \end{array}$$

This is a local antimagic 3-coloring for $\theta (6,6,2,2,4,2,2)=\theta (2,2,2,2,4,6,6)$ with colors 24, 25, 90.

4.3. From Spider Graphs

A spider graph with $s\ge 2$ legs, denoted by $Sp(a_1,a_2,\cdots ,a_s)$, is a tree formed by identifying an end-vertex, called the core vertex, of each path of length $a_i$ for each $1\le i\le s$, where $1\le a_1\le \cdots \le a_s$. In [6], the authors obtained many sufficient conditions so that ${\chi }_{la}\left(Sp(a_1,a_2,\dots ,a_s)\right)=s+1$. Motivated by this, we will construct some s-bridge graphs from some $Sp(a_1,a_2,\dots ,a_s)$ so that their local antimagic chromatic number is 3.

Theorem 9

([6], Theorem 2.11). Let $a_1,\dots ,a_s$ be positive even numbers, where $s\ge 2$. If $a_s=a_{s-2}+2a_{s-3}+\cdots +(s-3)a_2+(s-2)a_1$, then ${\chi }_{la}\left(Sp(a_1,\dots ,a_s)\right)=s+1$.

When $s=2$, the spider is a path. It is known [1] (Theorem 2.7) that the local antimagic chromatic number of a path of length at least 2 is 3. Actually, the condition of Theorem 9 does not hold when $s=2$. So we only consider $s\ge 3$. From the proof of [6] (Theorem 2.11), the core vertex has the induced color q, and all vertices of degree 2 are labeled by q or $q+1$, where q is the size of the spider graph. Now, we merge all pendant vertices. Then, we obtain an s-bridge graph and a local antimagic 3-coloring for the resulting graph. Therefore, we obtain the following result.

Corollary 2.

Let $a_1,\dots ,a_s$ be positive even numbers, where $s\ge 3$. If $a_s=a_{s-2}+2a_{s-3}+\cdots +(s-3)a_2+(s-2)a_1$, then ${\chi }_{la}\left(\theta (a_1,\dots ,a_s)\right)=3$.

Proof. 

From the above discussion, ${\chi }_{la}\left(\theta (a_1,\dots ,a_s)\right)\le 3$. It suffices to check that all graphs listed in Theorem 1 do not satisfy the condition of Corollary 2.

From the condition of Corollary 2, we have that when $s\ge 4$,

$$a_s\ge (s-4)a_3+(s-3)a_2+(s-2)a_1.$$

Also, all graphs listed in Theorem 1 are s-bridge graphs with $s\ge 4$. Next, we show that all graphs listed in Theorem 1 do not satisfy (1).

(1)

$\theta (4l^{[3l+2]},{(4l+2)}^{\left[l\right]})$, where $l\ge 1$.

Since $s=4l+2$, $a_1=4l$ and $a_s=4l+2$, it is clear that it does not satisfy (1).

(2a)

$\theta (2l-2,{(4l-2)}^{[3l-1]})$, where $l\ge 2$.

Since $s=3l$, $a_1=2l-2$ and $a_s=4l-2$, it is clear that it does not satisfy (1).

(2b)

$\theta (2,4^{\left[3\right]},6)$; $\theta (4,8^{\left[5\right]},{10}^{\left[2\right]})$; $\theta (6,{12}^{\left[7\right]},{14}^{\left[3\right]})$.

Clearly, each graph does not satisfy (1).

(3a)

$\theta (4l-2-2t,2t,{(4l-4)}^{\left[l\right]},{(4l-2)}^{[l-2]})$, where $2\le l\le t\le {\displaystyle \frac{5l-2}{4}}$.

Here, $4\le 2l\le 2t\le {\displaystyle \frac{5l}{2}}-1$. Thus, $s=2l$, $a_s=4l-2$ and $\{a_1,a_2\}=\{4l-2-2t,2t\}$. Then,

$$(s-3)a_2+(s-2)a_1>(s-3)(a_1+a_2)=(2l-3)(4l-2)\ge 4l-2,$$

implying that it does not satisfy (1).

(3b)

$\theta (4l-2-2t,2t-2,{(4l-4)}^{[l-1]},{(4l-2)}^{[l-1]})$, where $2\le l\le t\le {\displaystyle \frac{5l}{4}}$.

Similar to $\left(3a\right)$, $s=2l$, $a_s=4l-2$ and $\{a_1,a_2\}=\{4l-2-2t,2t-2\}$. When $l\ge 3$,

$$(s-3)a_2+(s-2)a_1>(s-3)(a_1+a_2)=(2l-3)(4l-4)\ge 4l-2.$$

When $l=2$, $\theta (4l-2-2t,2t-2,{(4l-4)}^{[l-1]},{(4l-2)}^{[l-1]})=\theta (2,2,20,22)$.

Clearly, $a_4\ne a_2+2a_1$.

(4)

$\theta (2t,4s-6-2t,2s-4,{(4s-6)}^{[s-3]})$, where ${\displaystyle \frac{2s-3}{8}}\le t\le {\displaystyle \frac{6s-5}{8}}$ and $s\ge 4$.

Obviously, $\{a_1,a_2,a_3\}=\{2t,4s-6-2t,2s-4\}$ and $s_s=4s-6$. When $s\ge 5$,

$$(s-4)a_3+(s-3)a_2+(s-2)a_1>a_1+a_2+a_3=6s-10>4s-6.$$

When $s=4$, $\theta (2t,4s-6-2t,2s-4,{(4s-6)}^{[s-3]})=\theta (2t,4,10-2t,10)$, where $t\in \{1,2\}$. Thus, $(s-4)a_3+(s-3)a_2+(s-2)a_1=a_2+2a_1=4+4t\ne 10=a_4$.

This completes the proof. □

4.4. From One-Point Unions of Cycles

A one-point union of $r\ge 2$ cycles, denoted by $C(n_1,n_2,\dots ,n_r)$, is a graph obtained by identifying a vertex of each cycle of order $n_1,n_2,\dots ,n_r\ge 3$. The vertex of degree $2r$ is called the core vertex, and its incident edges are called the central edges. The authors completely determined the local antimagic chromatic number of $C(n_1,n_2,\dots ,n_r)$. Motivated by this, we will construct some s-bridge graphs from some $C(n_1,n_2,\dots ,n_r)$ so that their local antimagic chromatic number is 3.

Note that if we choose a vertex of degree 2 in each cycle of $C(n_1,n_2,\dots ,n_r)$ and merge these r vertices into a vertex of degree $2r$ such that the graph is still simple, then we obtain a $2r$-bridge graph. For example, from $C(4,4)$, we can obtain $\theta (1,2,2,3)$ and $\theta (2,2,2,2)$.

Lemma 3.

Let G be a graph of size q. Suppose that there is a local antimagic labeling of G inducing a 2-coloring of G with colors x and y, where $x<y$. Let X and Y be the sets of vertices colored x and y, respectively. Then, G is a bipartite graph with bipartition $(X,Y)$ and $\left|X\right|>\left|Y\right|$. Moreover, $x\left|X\right|=y\left|Y\right|={\displaystyle \frac{q(q+1)}{2}}$.

Theorem 10.

For $G=C(n_1,n_2,\dots ,n_r)$, ${\chi }_{la}\left(G\right)=2$ if and only if $G=C({(4r-2)}^{[r-1]},2r-2)$, where $r\ge 3$, or $G=C({\left(2r\right)}^{\left[\right(r-1)/2]},{(2r-2)}^{\left[\right(r+1)/2]})$, where r is odd. Otherwise, ${\chi }_{la}\left(G\right)=3$.

Remark 2.

For completeness, we will give the local antimagic 2-coloring f for the graphs $G=C({(4r-2)}^{[r-1]},2r-2)$, where $r\ge 3$, and $G=C({\left(2r\right)}^{\left[\right(r-1)/2]},{(2r-2)}^{\left[\right(r+1)/2]})$, where r is odd. For $1\le i\le r$, the edges of the i-th cycle, $C_{n_i}$, has consecutive edges $e_{i,1},e_{i,2},\dots ,e_{i,n_i}$, with the central edges $e_{i,1}$ and $e_{i,n_i}$ incident to the core vertex u.

(A) 

Consider $G=C({(4r-2)}^{[r-1]},2r-2)$ for $r\ge 3$.

For the i-th $C_{4r-2}$, we label the edges $e_{i,2j-1}$ by $i+(2r-1)(j-1)$ and $e_{i,2j}$ by $4r^2-2r-i-(2r-1)j$, where $1\le j\le 2r-1$. For $C_{2r-2}$, we label the edges $e_{r,2j-1}$ by $(2r-1)j$ and $e_{r,2j}$ by $4r^2-4r+1-(2r-1)j$ for $1\le j\le r-1$. Then, the induced vertex labels are $y=4r^2-2r$ and $x=4r^2-4r+1$ alternately beginning at vertex u.

(B) 

Consider $G=C({\left(2r\right)}^{\left[\right(r-1)/2]},{(2r-2)}^{\left[\right(r+1)/2]})$ when r is odd.

For the i-th $C_{2r}$, where $1\le i\le (r-1)/2$, we label the edges $e_{i,2j-1}$ by $i+2r(j-1)$ and $e_{i,2j}$ by $2r^2-r-i-2r(j-1)$ for $1\le j\le r$. For the k-th $C_{2r-2}$, where $1\le k\le (r+1)/2$, we label the edges $e_{k,2j-1}$ by $-r+k-1+2rj$ and $e_{k,2j}$ by $2r^2-k+1-2rj$, $1\le j\le r-1$. Then, the induced vertex labels are $y=2r^2+r$ and $x=2r^2-r$ alternately beginning at vertex u.

Example 7.

For $C(10,10,4)$, beginning and ending with central edges, the two 10-cycles have the consecutive labels 1, 24, 6, 19, 11, 14, 16, 9, 21, 4 and 2, 23, 7, 18, 12, 13, 17, 8, 22, 3, respectively, while the 4-cycle has the consecutive labels 5, 20, 10, 15, with $y=30$ and $x=25$.

For $C(10,10,8,8,8)$, the two 10-cycles have the consecutive labels 1, 44, 11, 34, 21, 24, 31, 14, 41, 4 and 2, 43, 12, 33, 22, 23, 32, 13, 42, 3, respectively, while the three 8-cycles have the consecutive labels 5, 40, 15, 30, 25, 20, 35, 10; 6, 39, 16, 29, 26, 19, 36, 9 and 7, 38, 17, 28, 27, 18, 37, 8, respectively, with $y=55$ and $x=45$.

Let $G=C({(4r-2)}^{[r-1]},2r-2)$, where $r\ge 3$, or $G=C({\left(2r\right)}^{\left[\right(r-1)/2]},{(2r-2)}^{\left[\right(r+1)/2]})$, where r is odd. Let the core vertex u of G and all other vertices of even distance from u be black vertices, and let the remaining vertices be white vertices. For $1\le i\le r$, we choose a white vertex of the i-th cycle of G, say $v_i$, such that, at most, one of them is adjacent to u in G. We identify vertices $v_1$ to $v_r$ to obtain a new vertex v.

Observe that each obtained graph is

(i)

A $2r$-bridge graph with u and v as the only two vertices of degree $2r$;

(ii)

Bipartite, with both partite sets of the same size, with ${\chi }_{la}\ge 3$ (by Lemma 3).

Note that the new graph is either $\theta (2h_1-1,4r-2h_1-1,\cdots ,2h_{r-1}-1,4r-2h_{r-1}-1,2h_r-1,2r-2h_r-1)$, where, at most, one of $2h_i-1$, $4r-2h_i-1$, $2h_r-1$, $2r-2h-1$ is 1 and $1\le i\le r-1$, or $\theta (2h_1-1,2r-2h_1+1,\cdots ,2h_{(r-1)/2}-1,2r-2h_{(r-1)/2}+1,2k_1-1,2r-2k_1-1,\cdots ,2k_{(r+1)/2}-1,2r-2k_{(r+1)/2}-1)$, where r is odd and, at most, one of $2h_i-1$, $2r-2h_i+1$, $2k_j-1$, $2r-2k_j-1$ is 1, $1\le i\le (r-1)/2$ and $1\le j\le (r+1)/2$. Clearly, these graphs are not in the list of Theorem 1.

Theorem 11.

For a simple graph $\theta =\theta (2h_1-1,4r-2h_1-1,\cdots ,2h_{r-1}-1,4r-2h_{r-1}-1,2h_r-1,2r-2h_r-1)$ or $\theta =\theta (2h_1-1,2r-2h_1+1,\cdots ,2h_{(r-1)/2}-1,2r-2h_{(r-1)/2}+1,2k_1-1,2r-2k_1-1,\cdots ,2k_{(r+1)/2}-1,2r-2k_{(r+1)/2}-1)$, ${\chi }_{la}\left(\theta \right)=3$.

Proof. 

Consider graphs obtained by the transformation given above. If $G=C({(4r-2)}^{[r-1]},2r-2)$, $r\ge 3$, we immediately have a bipartite $2r$-bridge graph that induces a local antimagic 3-coloring with vertex labels $y=4r^2-2r$ and $x=4r^2-4r+1$ alternately beginning at vertex u, whereas vertex v has the label $rx=r(4r^2-4r+1)$.

Similarly, if $G=C({\left(2r\right)}^{\left[\right(r-1)/2]},{(2r-2)}^{\left[\right(r+1)/2]})$, and r is odd, we immediately have a bipartite $2r$-bridge graph that induces a local antimagic 3-coloring with vertex labels $y=2r^2+r$ and $x=2r^2-r$ alternately beginning at vertex u, whereas vertex v has the label $rx=r^2(2r-1)$. Thus, this labeling is a local antimagic 3-coloring. □

Example 8.

Suppose $G=C(10,10,4)$. Let $d(u,v_i)=d_i$, where $i\in \{1,2,3\}$, the distance between u and $v_i$. We have $(d_1,d_2,d_3)\in \{(3,3,1),(3,5,1),(5,5,1)\}$. So, the bipartite 6-bridge graphs are $\theta (1,3,3,3,7,7)$, $\theta (1,3,3,5,5,7)$ and $\theta (1,3,5,5,5,5)$, respectively. A local antimagic 3-coloring for $\theta (1,3,3,5,5,7)$ with colors 25, 30, 75 is given in Figure 2.

Note that in transforming $C(n_1,n_2,\dots ,n_r)$ to $2r$-bridge graphs, if at least a black vertex and at least a white vertex are chosen, the $2r$-bridge graphs must be tripartite (in this paper, a tripartite graph means that the chromatic number of the graph is 3). Let the number of chosen black vertices be k, $1\le k\le r-1$.

Theorem 12.

For even $s\ge 4$, there are infinitely many tripartite s-bridge graphs θ with ${\chi }_{la}\left(\theta \right)=3$.

Proof. 

Consider the tripartite $2r$-bridge graphs obtained above. If $G=C({(4r-2)}^{[r-1]},2r-2)$, $r\ge 3$, we immediately have a tripartite $2r$-bridge graph that induces a local antimagic 3-coloring with vertex labels $y=4r^2-2r$ and $x=4r^2-4r+1$ alternately beginning at vertex u, whereas vertex v has the label $ky+(r-k)x=k(4r^2-2r)+(r-k)(4r^2-4r+1)$. Similarly, if $G=C({\left(2r\right)}^{\left[\right(r-1)/2]},{(2r-2)}^{\left[\right(r+1)/2]})$, and r is odd, we immediately have a tripartite $2r$-bridge graph that induces a local antimagic 3-coloring with the vertex labels $y=2r^2+r$ and $x=2r^2-r$ alternately beginning at vertex u, whereas vertex v has the label $ky+(r-k)x=k(2r^2+r)+(r-k)(2r^2-r)$. Thus, ${\chi }_{la}\left(G\right)\le 3$. Since $\chi \left(G\right)=3$, the theorem holds. □

Example 9.

Suppose $G=C(10,10,4)$. Suppose that both $d_1=d(u,v_1)$, $d_2=d(u,v_2)$ are odd, and $d_3=d(u,v_3)$ is even, i.e., $k=1$.

We must have $(d_1,d_2,d_3)\in \{(1,3,2),(1,5,2),(3,3,2),(3,5,2),(5,5,2)\}$. So, the tripartite 6-bridge graphs are $\theta (1,2,2,3,7,9)$, $\theta (1,2,2,5,5,9)$, $\theta (2,2,3,3,7,7)$, $\theta (2,2,3,5,5,7)$ and $\theta (2,2,5,5,5,5)$, respectively. A local antimagic 3-coloring for $\theta (2,2,5,5,5,5)$ with colors 25, 30, 80 is given in Figure 3.

5. Conclusions and Future Works

In this paper, we obtained many families of either bipartite or tripartite bridge graphs with local antimagic chromatic number 3. In [10], the authors proposed an application of local antimagic vertex coloring in optimizing factory workers’ work shift scheduling. A similar application using the idea of the local antimagic total labeling of a graph is given in [11]. With the development of science and technology, it is expected that local antimagic chromatic numbers can also have useful applications in the future.

Since no bridge graph with a local antimagic chromatic number greater than 3 is known, the following conjecture, which is partially supported by our results obtained herein, arises naturally.

Conjecture 1.

Every bridge graph not in Theorem 1 has local antimagic chromatic number 3.