AVD edge-colorings of cubic Halin graphs

1.   Introduction

All graphs considered in this paper are simple, finite and undirected. Let $G = (V, E)$ be a graph with maximum degree $\Delta$ and $c:E\to \{1, 2, \ldots, k\}$ be an edge-coloring of $G$. For each vertex $v\in V$, the neighborhood $N(v)$ of $v$ is $N(v) = \{u:u\in V, \; uv\in E\}$, we define the palette of $v$ as $S(v) = \{ c(uv):u\in N(v) \}$, and denote by $S^c(v)$ the complementary set of $S(v)$ in $\{1, 2, \ldots, k\}$. We call $c$ a proper edge-coloring if it assigns distinct colors to adjacent edges. The minimum number of colors needed in a proper edge-coloring is the chromatic index of $G$, denoted by $\chi'(G)$. An adjacent vertex-distinguishing edge-coloring (AVD edge-coloring for short) of $G$ is a proper edge-coloring $c$ such that $S(v)\ne S(u)$ for each $uv\in E$. The smallest integer $k$ such that $G$ has an AVD edge-coloring with $k$ colors is called the adjacent vertex-distinguishing chromatic index (AVD chormatic index for short), denoted by $\chi'_{avd}(G)$. Note that $G$ has an AVD edge-coloring if and only if $G$ has no isolated edges, we call this graph a normal graph. From the definition, for a normal graph $G$, we have $\chi'_{avd}(G)\ge \chi'(G)\ge \Delta$, and if $G$ contains two adjacent vertices of maximum degree, then $\chi'_{avd}(G)\ge \Delta+1$.

The concept of AVD edge-coloring was first introduced by Zhang et al. ^[1], they completely determined $\chi_{avd}'(G)$ for some special graphs such as paths, cycles, trees, complete graphs, and complete bipartite graphs, and proposed the following conjecture.

Conjecture 1.1. ^[1] If $G$ is a normal connected graph with $|V(G)|\ge 3$ and $G\neq C_5$. Then $\chi_{avd}'(G)\leq \Delta(G)+2$.

Balister et al. ^[2] comfirmed Conjecture 1.1 for all graphs with maximum degree 3.

Theorem 1.1. ^[2] If $G$ is a graph with no isolated edges and $\Delta = 3$, then $\chi_{avd}'(G)\leq 5$.

They showed that Conjecture 1.1 is also true for bipartite graphs, and if the chromatic number of $G$ is $k$, then $\chi_{avd}'(G)\leq \Delta(G)+O(log k)$. By using probabilistic method, Hatami ^[3] proved that $\chi_{avd}'(G)\leq \Delta(G)+300$ for graphs $G$ with maximum degree $\Delta \ge 10^{20}$. Joret et al. ^[4] reduced this bound to $\Delta +19$. Horňák et al. ^[5] showed that Conjecture 1.1 holds for planar graphs with maximum degree at least 12. Yu et al. ^[6] verified this conjecture for graphs with maximum degree at least 5 and maximum average degree less than 3. In addition, there are many graphs with adjacent vertex-distinguishing chromatic indices at most $\Delta(G)+1$. Hocquard and Montassier^[7] showed that $\chi_{avd}'(G)\leq \Delta(G)+1$ for graphs with $\Delta(G)\geq 5$ and ${\rm{mad}}(G) < 2-\frac{2}{\Delta(G)}$. Bonamy and Przybyło ^[8] proved that for any planar graph $G$ with $\Delta(G)\ge 28$ and no isolated edges, $\chi_{avd}'(G)\leq \Delta(G)+1$. Huang et al. ^[9] showed that $\chi_{avd}'(G)\leq \Delta(G)+1$ holds for every connected planar graph $G$ without 3-cycles and with maximum degree at least 12.

Wang et al. ^[10] proved that $\chi_{avd}'(G)\leq max\{6, \Delta(G)+1\}$ for any 2-degenerate graph $G$ without isolated edges. Wang and Wang ^[11] characterized the adjacent vertex-distinguishing chromatic indices for $K_4$-minor graphs. Cubic Halin graphs is an important class of graphs, Chang and Liu ^[12] considered the strong edge-coloring of cubic Halin graphs. In this paper, we will study the adjacent vertex-distinguishing edge-coloring of cubic Halin graphs.

A Halin graph $G$ is a plane embedding of a tree $T$ and a cycle $C$, where the inner vertices of $T$ have minimum degree at least 3, and the cycle $C$ connects all the leaves of $T$ in such a way that $C$ is the boundary of the exterior face. The tree $T$ and the cycle $C$ are called the characteristic tree and the adjoint cycle of $G$, respectively.

A caterpillar is a tree whose removal of leaves results in a path $P$ (called spine of the caterpillar). Let $\mathcal{G}_r$ be the set of all cubic Halin graphs whose characteristic trees are caterpillars with $r+2$ leaves. For a Halin graph $G = T\cup C$ in $\mathcal{G}_r$, denote the spine $P$ of $T$ as $P = v_1v_2\ldots v_r$, let $u_0$, $u_1$ be the neighbors of $v_1$ other than $v_2$, and $u_r$, $u_{r+1}$ be the neighbors of $v_r$ other than $v_{r-1}$. For $2\le i\le r-1$, let $u_i$ be the neighbor of $v_i$ that is a leaf of $T$. Moreover, assume that $u_1u_2\in E(G)$ and $u_{r-1}u_{r}\in E(G)$. Let $v$ be a vertex of $P$. We call $u$ a leaf-neighbor of $v$ if $u$ is adjacent to $v$ and is of degree 1 in $T$, and the edge $uv$ is called the leaf-edge. We draw $G$ on the plane by putting the spine $P$ vertically in the middle, and the leaf-edges incident with $v_i$, $2\le i\le r-1$, either left or right edges horizontally to $P$. See Figure 1 for an example of $\mathcal{G}_8$.

In particular, if all the leaf-neighbors are on the same side of $P$, then we call this graph $G$ a necklace and denote by $N_r$. We give configurations of $N_4$ and $N_5$ in Figure 2.

It's easy to see that $\chi'_{avd}(G)\ge 4$ for any cubic graph $G$. By Theorem 1.1, the adjacent vertex-distinguishing chromatic index for any cubic Halin graph is at most 5. Hence, for any cubic Halin graph $G$, we have either $\chi'_{avd}(G) = 4$ or $\chi'_{avd}(G) = 5$. Thus it is interesting to determine the exact value of $\chi'_{avd}(G)$. In this paper, we consider the cubic Halin graphs in $\mathcal{G}_r$, and show that there are only two graphs in $\mathcal{G}_r$ with the AVD chromatic index 5.

Theorem 1.2. Let $r\geq 2$ be an integer and $G\in \mathcal{G}_r$. Then $\chi_{avd}'(G) = 4$ if $G\notin \{N_4, N_5\}$; otherwise $\chi_{avd}'(G) = 5$.

2.   Proof of Theorem 1.2

Let $G$ be a cubic Halin graph in $\mathcal{G}_r$. We define the subgraphs induced by $\{u_1v_1, u_0u_1, u_0v_1, u_1u_2, v_1v_2, u_0u_x\}$ and $\{u_ru_{r+1}, u_rv_r, v_ru_{r+1}, u_{r-1}u_{r}, v_{r-1}v_r, u_yu_{r+1}\}$ as end-graphs of $G$, where $u_x$ and $u_y$ are the neighbors of $u_0$ and $u_{r+1}$, see Figure 3 for an illustration. We denote these two subgraphs by $G_1$ and $G_r$, respectively. For a vertex $u_i$ ($2\le i\le r-1$), we will use $u_i'$ and $u_i''$ to denote the neighbors of $u_i$ that are on the cycle if the neighbors of $u_i$ are uncertain, where $u_i'$ is closer to the end-graph $G_1$. For $2\le i\le r-1$, if the leaf-neighbors of $v_i, v_{i+1}, \ldots, v_{i+k-1}$ are on the same side of $P$, while $v_{i-1}$ and $v_{i+k}$ have leaf-neighbors on the other side. Then the subgraph induced by $\{v_{i}, v_{i+1}, \ldots, v_{i+k-1}, u_i, u_{i+1}, \ldots, u_{i+k-1}\}$ accompanied by the extra edges $v_{i+k-1}v_{i+k}$ and $u_{i+k-1}u_{i+k-1}''$ is called a $k$-block, denoted by $G_{i, k}$. If a $k$-block contains the vertex $v_r$, then the block is a bottom block of $G$. See the graph $H_0$ in Figure 1, the subgraph induced by $\{u_6, v_6, u_7, v_7\}$ accompanied by the edges $u_7u_8$ and $v_7v_8$ is the 2-block $G_{6, 2}$ and it is a bottom block. For two blocks $G_{i, k}$ and $G_{j, t}$, if $v_{i+k} = v_j$ or $v_{j+t} = v_i$, then we say $G_{i, k}$ and $G_{j, t}$ are adjacent. If $v_{i+k}\le v_j$, then we say $G_{i, k}$ is before $G_{j, t}$. We call a subgraph obtained from the union of $k$ adjacent 1-block a $k$-crossing block, or crossing block for short, of $G$. We denote the $k$-crossing block obtained from the union of $G_{i, 1}, \; G_{i+1, 1}, \; \ldots, \; G_{i+k-1, 1}$ as $G_{i, k, c}$. In Figure 1, the graph induced by the edges $\{v_4u_4, v_4v_5, u_4u_6, v_5u_5, v_5v_6, u_5u_9\}$ is the 2-crossing block $G_{4, 2, c}$.

A coloring of $G$ is good, if it is an AVD-edge-coloring of $G$ using colors in $\{1, 2, 3, 4\}$. To prove Theorem 1.2, we will give a good coloring of $G$ by coloring the edges of $G$ from the top down. Initially we establish a good coloring of the end-graph $G_1$, then we extend this coloring to the block that contains $u_2v_2$. By analyzing the coloring of $G_1$ and the block containing $u_2v_2$, we proceed to color the block that is adjacent to the block containing $u_2v_2$. Repeat this process until we complete the coloring of the bottom block and the end-graph $G_r$.

In the following, given an edge-coloring $c$ of a graph $G$, we define a vertex coloring $\overline{c}$ respect to $c$ as follows: for each vertex $v\in V(G)$, let $\overline{c}(v)$ be an element in $S^c(v)$, that is, $\overline{c}(v)$ is the color that is not appeared at the edges incident with $v$. Note that if $c$ is a good coloring of $G$, $uv\in E(G)$, and $d(u) = d(v) = 3$, then $\overline{c}(u)$ and $\overline{c}(v)$ are unique, and $\overline{c}(u)\neq \overline{c}(v)$. Now we consider the colorings of the end-graphs.

Proposition 2.1. Let $G_1$ be an end-graph with vertex set $\{u_1, u_2, v_1, v_2, u_0, u_x\}$. If $G_1$ admits a good coloring, then at least two edges of $u_1u_2, \; v_1v_2,$ and $u_0u_x$ are colored the same. Moreover, there are four types of good colorings of $G_1$:

(1) $c(u_1u_2) = c(v_1v_2) = c(u_0u_x)$, $c(u_1v_1) = \overline{c}(u_0)$, $\; c(u_0v_1) = \overline{c}(u_1), \; c(u_0u_1) = \overline{c}(v_1)$;

(2) $c(u_1u_2) = c(v_1v_2)\neq c(u_0u_x)$, $c(u_0v_1) = \overline{c}(u_1)$, $c(u_0u_1) = \overline{c}(v_1), \; c(u_1u_2) = \overline{c}(u_0)$;

(3) $c(u_1u_2) = c(u_0u_x)\neq c(v_1v_2)$, $c(u_1v_1) = \overline{c}(u_0)$, $c(u_0v_1) = \overline{c}(u_1), \; c(u_1u_2) = \overline{c}(v_1)$;

(4) $c(v_1v_2) = c(u_0u_x)\neq c(u_1u_2)$, $c(u_1v_1) = \overline{c}(u_0)$, $c(u_0u_1) = \overline{c}(v_1), \; c(v_1v_2) = \overline{c}(u_1)$.

Proof. Suppose that $G_1$ has a good coloring $\phi$. If $u_1u_2, \; v_1v_2,$ and $u_0u_x$ are colored with distinct colors, without loss of generality, assume that $\phi(u_1u_2) = 1, \; \phi(v_1v_2) = 2$ and $\phi(u_0u_x) = 3$, then $\phi(u_0u_1)\in \{2, 4\}$. If $\phi(u_0u_1) = 4$, then $\phi(u_1v_1) = 3$ and $\phi(u_0v_1) = 1$. But then $S(u_0) = S(u_1)$, contradicts that $\phi$ is a good coloring. Hence $\phi(u_0u_1) = 2$. No matter what color of $u_1v_1$ is, we always have $S(u_1) = S(v_1)$, so $\phi$ cannot be a good coloring. Therefore, at least two edges of $u_1u_2, \; v_1v_2,$ and $u_0u_x$ are colored the same.

There are four types of colorings on the edges $u_1u_2, \; v_1v_2$ and $u_0u_x$ such that at least two of them are colored the same, each type we will obtain a good coloring of $G_1$. Let $c$ be a coloring of the edges $u_1u_2, \; v_1v_2$ and $u_0u_x$.

Type (1): $c(u_1u_2) = c(v_1v_2) = c(u_0u_x)$. Then color $u_0u_1, \; u_0v_1, \; v_1u_1$ with three distinct colors in $\{1, 2, 3, 4\}$ that are different from $c(u_1u_2)$. Thus, $c$ is a good coloring of $G_1$, and $c(u_1v_1) = \overline{c}(u_0)$, $\; c(u_0v_1) = \overline{c}(u_1), \; c(u_0u_1) = \overline{c}(v_1)$.

Type (2): $c(u_1u_2) = c(v_1v_2)\neq c(u_0u_x)$. Then color $u_0u_1$, $u_0v_1$ with distinct colors in $\{1, 2, 3, 4\}\backslash \{c(u_1u_2), c(u_0u_x)\}$, and color $u_1v_1$ with $c(u_0u_x)$. Thus, $c$ is a good coloring of $G_1$, and $c(u_0v_1) = \overline{c}(u_1)$, $c(u_0u_1) = \overline{c}(v_1), \; c(u_1u_2) = \overline{c}(u_0)$.

Type (3): $c(u_1u_2) = c(u_0u_x)\neq c(v_1v_2)$. Then color $u_1v_1$, $u_0v_1$ with distinct colors in $\{1, 2, 3, 4\}\backslash \{c(v_1v_2), c(u_0u_x)\}$, and color $u_0u_1$ with $c(v_1v_2)$. Thus, $c$ is a good coloring of $G_1$, and $c(u_1v_1) = \overline{c}(u_0)$, $c(u_0v_1) = \overline{c}(u_1), \; c(u_1u_2) = \overline{c}(v_1)$.

Type (4): $c(v_1v_2) = c(u_0u_x)\neq c(u_1u_2)$. Then color $u_0u_1$, $u_1v_1$ distinct colors in $\{1, 2, 3, 4\}\backslash \{c(u_1u_2), c(v_1v_2)\}$, and color $u_0v_1$ is with $c(u_1u_2)$. Thus, $c$ is a good coloring of $G_1$, and $c(u_1v_1) = \overline{c}(u_0)$, $c(u_0u_1) = \overline{c}(v_1), \; c(v_1v_2) = \overline{c}(u_1)$.

Therefore, we complete the proof of this proposition. □

Remark 2.1. The results of Proposition 2.1 is also holds for the end-graph $G_r$, that is, if $G_r$ admits a good coloring, then at least two edges of $u_{r-1}u_{r}, v_{r-1}v_r, u_yu_{r+1}$ are colored the same.

Lemma 2.1. Let $G$ be a graph in $\mathcal{G}_r$, and $G'$ be the graph obtained from $G$ by deleting edges $u_rv_r, v_ru_{r+1}$, and $u_ru_{r+1}$. Suppose that $G'$ has a good coloring $c$, then $c$ can be extended to a good coloring of $G$ if and only if one of the following statements holds:

(1) $c(u_{r-1}u_r) = c(v_{r-1}v_r) = c(u_yu_{r+1})$;

(2) $c(u_{r-1}u_r) = c(v_{r-1}v_r)\neq c(u_yu_{r+1})$ and $\overline{c}(u_y)\neq c(u_{r-1}u_r)$;

(3) $c(u_{r-1}u_r) = c(u_yu_{r+1})\neq c(v_{r-1}v_r)$ and $\overline{c}(v_{r-1})\neq c(u_{r-1}u_r)$, moreover, if $\overline{c}(u_{r-1}) = \overline{c}(u_y)$, then they are equal to $c(v_{r-1}v_r)$;

(4) $c(v_{r-1}v_r) = c(u_yu_{r+1})\neq c(u_{r-1}u_r)$ and $\overline{c}(u_{r-1})\neq c(v_{r-1}v_r)$, moreover, if $\overline{c}(v_{r-1}) = \overline{c}(u_{y})$, then they are equal to $c(u_{r-1}v_r)$.

Proof. Suppose $c$ is extended to a good coloring of $G$, then $c$ is a good coloring of $G_r$. By Remark 2.1, at least two edges of $u_{r-1}u_r, \; v_{r-1}v_r,$ and $u_yu_{r+1}$ are colored the same. If all three edges $u_{r-1}u_r, \; v_{r-1}v_r,$ and $u_yu_{r+1}$ are colored the same, then statement (1) holds. Otherwise, exactly two edges of them are colored the same.

If $c(u_{r-1}u_r) = c(v_{r-1}v_r)\neq c(u_yu_{r+1})$, then $c(v_ru_{r+1})\neq c(u_{r-1}u_r)$ since $c(v_ru_{r+1})\neq c(v_{r-1}v_r)$. Furthermore, $c(u_ru_{r+1})\neq c(u_{r-1}u_r)$ and $c(u_yu_{r+1})\neq c(u_{r-1}u_r)$, hence $c(u_{r-1}u_r)$ does not appear at the edges incident with $u_{r+1}$, it follows that $\overline{c}(u_{r+1}) = c(u_{r-1}u_r)$. Because $\overline{c}(u_y)\neq \overline{c}(u_{r+1})$, we have $\overline{c}(u_y)\neq c(u_{r-1}u_r)$.

If $c(u_{r-1}u_r) = c(u_yu_{r+1})\neq c(v_{r-1}v_r)$, without loss of generality, assume that $c(u_{r-1}u_r) = c(u_yu_{r+1}) = 1$, $c(v_{r-1}v_r) = 2$, then $c(u_rv_r)\neq 1$ and $c(v_ru_{r+1})\neq 1$, hence $\overline{c}(v_r) = 1$, which implies that $\overline{c}(v_{r-1})\neq 1$, that is, $\overline{c}(v_{r-1})\neq c(u_{r-1}u_r)$. Furthermore, if $\overline{c}(u_{r-1}) = \overline{c}(u_y)$, then $\overline{c}(u_{r-1})$ must appear on $u_ru_{r+1}$. If $\overline{c}(u_{r-1})\neq c(v_{r-1}v_r)$, then $\overline{c}(u_{r-1})\in \{3, 4\}$. If $\overline{c}(u_{r-1}) = 3$, then $c(u_ru_{r+1}) = 3$, so $c(u_rv_r) = 4$, and $v_ru_{r+1}$ cannot be colored. If $\overline{c}(u_{r-1}) = 4$, then $c(u_ru_{r+1}) = 4$, so $c(u_rv_r) = 3$, and $v_ru_{r+1}$ cannot be colored. Therefore, $\overline{c}(u_{r-1}) = c(v_{r-1}v_r)$.

If $c(v_{r-1}v_r) = c(u_yu_{r+1})\neq c(u_{r-1}u_r)$, by the same analysis as case $c(u_{r-1}u_r) = c(u_yu_{r+1})\neq c(v_{r-1}v_r)$, we have $\overline{c}(u_{r-1})\neq c(v_{r-1}v_r)$, and if $\overline{c}(v_{r-1}) = \overline{c}(u_{y})$, then they must equal to $c(u_{r-1}v_r)$.

Therefore, if $c$ is extended to a good coloring of $G$, then one of the statements (1)–(4) holds.

On the other hand, we show that if $c$ satisfies one of the statements (1)–(4), then $c$ can be extended to a good coloring of $G$.

Suppose that $c$ satisfies statment (1), that is, $c(u_{r-1}u_r) = c(v_{r-1}v_r) = c(u_yu_{r+1})$. Since $u_{r-1}v_{r-1}\in E(G')$, we have $\overline{c}(u_{r-1})\neq \overline{c}(v_{r-1})$. If $\overline{c}(u_y)$ is distinct from $\overline{c}(u_{r-1})$ and $\overline{c}(v_{r-1})$, then let $c(u_rv_r) = \overline{c}(u_{r-1}), \; c(v_ru_{r+1}) = \overline{c}(v_{r-1}), \; c(u_ru_{r+1}) = \overline{c}(u_y)$. It is easy to see that $c$ is a good coloring of $G$. If $\overline{c}(u_y)$ is equal to $\overline{c}(u_{r-1})$ or $\overline{c}(v_{r-1})$, without loss of generality, assume that $\overline{c}(u_y) = \overline{c}(u_{r-1})$, then let $c(u_ru_{r+1}) = \overline{c}(u_y), \; c(u_rv_r) = \overline{c}(v_{r-1}), \; c(v_ru_{r+1}) = \{1, 2, 3, 4\}\backslash\{\overline{c}(u_y), \overline{c}(v_{r-1}), c(v_{r-1}v_r)\}$. Then $c$ is a good coloring of $G$.

Now suppose that $c$ satisfies statment (2), that is, $c(u_{r-1}u_r) = c(v_{r-1}v_r)\neq c(u_yu_{r+1})$. Without loss of generality, assume that $c(u_{r-1}u_r) = c(v_{r-1}v_r) = 1$ and $c(u_yu_{r+1}) = 2$. By statement (2), $\overline{c}(u_y)\neq 1$. If $\overline{c}(u_{r-1}) = 2$, then let $c(u_rv_r) = 2, \; c(v_ru_{r+1}) = \overline{c}(v_{r-1})$, and $c(u_ru_{r+1}) = \{1, 2, 3, 4\}\backslash\{1, 2, \overline{c}(v_{r-1})\}$. If $\overline{c}(v_{r-1}) = 2$, then let $c(u_rv_r) = 2, \; c(u_ru_{r+1}) = \overline{c}(u_{r-1})$, and $c(v_ru_{r+1}) = \{1, 2, 3, 4\}\backslash\{1, 2, \overline{c}(u_{r-1})\}$. If $\overline{c}(u_{r-1})\neq 2$ and $\overline{c}(v_{r-1})\neq 2$, then let $c(u_rv_r) = 2, \; c(u_ru_{r+1}) = \overline{c}(u_{r-1})$, and $c(v_ru_{r+1}) = \overline{c}(v_{r-1})$. Note that $\overline{c}(u_{r-1})\neq 1$, $\overline{c}(v_{r-1})\neq 1$, and $\overline{c}(u_{r-1})\neq \overline{c}(v_{r-1})$, hence all the colorings above are good colorings of $G$.

Next suppose that $c$ satisfies statment (3), that is, $c(u_{r-1}u_r) = c(u_yu_{r+1})\neq c(v_{r-1}v_r)$. Without loss of generality, assume that $c(u_{r-1}u_r) = c(u_yu_{r+1}) = 1$ and $c(v_{r-1}v_r) = 2$. If $\overline{c}(u_{r-1}) = \overline{c}(u_y)$, by statement (3), $\overline{c}(u_{r-1}) = \overline{c}(u_y) = 2$, then let $c(u_ru_{r+1}) = 2, \; c(u_rv_r) = \overline{c}(v_{r-1})$, and $c(v_ru_{r+1}) = \; \{1, 2, 3, 4\}\backslash\{1, 2, \overline{c}(v_{r-1})\}$. If $\overline{c}(u_{r-1}) = 2, \; \overline{c}(u_y)\neq 2$, then let $c(u_ru_{r+1}) = 2, \; c(u_rv_r) = \overline{c}(v_{r-1})$, and $c(v_ru_{r+1}) = \{1, 2, 3, 4\}\backslash\{1, 2, \overline{c}(v_{r-1})\}$. If $\overline{c}(u_{r-1})\neq 2$, then let $c(u_rv_r) = \overline{c}(u_{r-1})$, $c(v_ru_{r+1}) = \overline{c}(v_{r-1})$ and $c(u_ru_{r+1})\in \{1, 2, 3, 4\}\backslash \{1, \overline{c}(u_{r-1}), \overline{c}(v_{r-1})\}$. Note that $\overline{c}(v_{r-1})\neq 2$, and by statement (3), we have $\overline{c}(v_{r-1})\neq 1$, hence $\overline{c}(v_{r-1})\in \{3, 4\}$. Therefore, we can check that the colorings above are good colorings of $G$.

The argument for statement (4) is similar as the argument for statement (3), hence we omit the proof here. □

Next we consider the coloring of the blocks. Let $G_{i, k}$ ($G_{i, k, c}$) be a $k$-block ($k$-crossing block), we define the associated subgraph $H_{i, k}$ ($H_{i, k, c}$) of $G_{i, k}$ ($G_{i, k, c}$) as the subgraph obtained by the union of $G_1$ and all the blocks before $G_{i, k}$ ($G_{i, k, c}$). To color $G_{i, k}$ or $G_{i, k, c}$, we assume that the associated subgraph $H_{i, k}$ has a good coloring $c$. Let $v_ju_j$ be an edge with $j\le i$. We define $\{c(v_{j-1}v_j), c(u_j'u_j), \overline{c}(v_{j-1}), \overline{c}(u_j')\}$ as the total-set of $v_ju_j$. If the total-set of $v_ju_j$ is $\{1, 2, 3, 4\}$, then we call $v_ju_j$ a full-edge. If $c(v_{j-1}v_j)\neq c(u_j'u_j), \; c(v_{j-1}v_j) = \overline{c}(u_j'), \; c(u_j'u_j)\neq \overline{c}(v_{j-1})$, then we call $v_ju_j$ an in-half-edge. If $c(v_{j-1}v_j)\neq c(u_j'u_j), \; c(u_j'u_j) = \overline{c}(v_{j-1}), \; c(v_{j-1}v_j)\neq \overline{c}(u_j')$, then we call $v_ju_j$ an out-half-edge. A half-edge means a in-half-edge or out-half-edge. The edge $v_ju_j$ is a crossing-edge if $c(u_j'u_j) = c(v_{j-1}v_j)$. Note that, if $v_ju_j$ is a crossing-edge, then $c(u_ju_j'') = \overline{c}(v_j)$ and $c(v_jv_{j+1}) = \overline{c}(u_j)$, and vice versa. For two edges $v_ju_j$ and $v_{j+1}u_{j+1}$, assume that $u_j$ and $u_{j+1}$ are on the different sides of $P$, we call $v_ju_j$ an outer-crossing-edge if $c(v_jv_{j+1}) = \overline{c}(u_j)$ and $c(u_ju_j'') = \overline{c}(u_{j+1}')$. If $c(u_ju_j'')\in \{\overline{c}(v_j), \; \overline{c}(u_{j+1}')\}$, then we call the color $c(u_ju_j'')$ suitable. Note that if $v_ju_j$ is a crossing-edge or outer-crossing-edge, then $c(u_ju_j'')$ is suitable.

Lemma 2.2. Let $G_{i, k}$ be a $k$-block with $k\ge 2$, suppose $H_{i, k}\cup G_{i, k}$ has a good coloring $c$ such that $v_ju_j$ is an in-half-edge(out-half-edge) for some $j$, $i\le j < i+k-1$, then for any $t$, $j < t\le i+k-1$, $v_tu_t$ is also an in-half-edge(out-half-edge).

Moreover, if $G_{i, k}$ is a bottom block and $v_ju_j$ is a half-edge, then $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1}) = c(u_{r-1}u_r)$ when $v_ju_j$ is an in-half-edge or $c(u_{i-1}u_{r+1}) = c(v_{r-1}v_r)$ when $v_ju_j$ is an out-half-edge.

Proof. We assume that $v_ju_j$ is an in-half-edge. Without loss of generality, suppose $c(v_{j-1}v_j) = \overline{c}(u_j') = \; 1$, $c(u_j'u_j) = 2$, and $\overline{c}(v_{j-1}) = 3$. Since $\overline{c}(u_j')$ must appear at the edges incident with $u_j$ and $c(v_ju_j)\neq 1$, we have that $c(u_ju_{j+1}) = 1$. If $c(v_jv_{j+1}) = 2$, then $S(v_j) = S(u_j)$, contradicts that $c$ is good coloring. So $c(v_jv_{j+1})\in \{3, 4\}$. If $c(v_jv_{j+1}) = 3$, then $c(v_ju_j) = 4$. If $c(v_jv_{j+1}) = 4$, then $c(v_ju_j) = 3$. No matter $v_jv_{j+1}$ is colored with $3$ or $4$, we have $c(v_jv_{j+1})\neq c(u_ju_{j+1})$, $c(v_jv_{j+1}) = \overline{c}(u_j)$, and $c(u_ju_{j+1})\neq \overline{c}(v_j)$. That is, the edge $v_{j+1}u_{j+1}$ is a in-half-edge. By the same argument, we have that for any $t$, $j < t\le i+k-1$, $v_tu_t$ is an in-half-edge. Furthermore, if $G_{i, k}$ is a bottom block, then $c(v_{r-1}v_r)\neq c(u_{r-1}u_r)$, $c(v_{r-1}v_r) = \overline{c}(u_{r-1})$, and $c(u_{r-1}u_r)\neq \overline{c}(v_{r-1})$. Statement (1), (2) and (4) of Lemma 2.1 can not hold. Hence $c$ can be extended to a good coloring of $G$ if and only if statement (3) of Lemma 2.1 holds. Since $c(u_{r-1}u_r)\neq \overline{c}(v_{r-1})$, we have $c(u_{i-1}u_{r+1}) = c(u_{r-1}u_r)$.

By the same argument as above, we can show that if $v_ju_j$ is an out-half-edge, then for any $t$, $j < t\le i+k-1$, $v_tu_t$ is also an out-half-edge. And if $G_{i, k}$ is a bottom block, then $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1}) = c(v_{r-1}v_r)$. □

Lemma 2.3. Let $G_{i, k}$ be a $k$-block with $k\ge 4$. Suppose $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is an in-half-edge (out-half-edge), then for any $\alpha \in \{1, 2, 3, 4\}$, $c$ can be extended to a good coloring of $G_{i, k}$ such that $c(u_{i+k-1}u_{i+k-1}'') = \alpha$ ($c(v_{i+k-1}v_{i+k}) = \alpha$).

Proof. Suppose $v_iu_i$ is an in-half-edge, without loss of generality, assume that $c(v_{i-1}v_i) = \overline{c}(u_i') = \; 1, \; c(u_i'u_i) = 2$, and $\overline{c}(v_{i-1}) = 3$. Then we have $c(u_iu_{i+1}) = 1$, and $c(v_iv_{i+1})\notin \{1, 2\}$. We color $v_iv_{i+1}$ with a color in $\{3, 4\}$ and color $v_{i+k-2}v_{i+k-1}$ with $\alpha$. For $i+1\le j\le i+k-3$, we color $v_jv_{j+1}$ with a color in $\{1, 2, 3, 4\}$ that is different from the colors of $v_{j-2}v_{j-1}$, $v_{j-1}v_j$ and $\alpha$, and color $v_{i+k-1}v_{i+k}$ with a color different from the colors of $v_{i+k-3}v_{i+k-2}$ and $v_{i+k-2}v_{i+k-1}$. Then set $c(u_ju_{j+1}) = c(v_{j-1}v_{j})$ for $i\le j\le i+k-2$ and $c(u_{i+k-1}u_{i+k-1}'') = \alpha$. Finally, for $i\le j\le i+k-1$, set $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(u_j'u_j), c(v_jv_{j+1}\}$. It is easy to see that this coloring $c$ is a good coloring of $G_{i, k}$ and $c(u_{i+k-1}u_{i+k-1}'') = \alpha$.

By symmetry, if $v_iu_i$ is an out-half-edge, then for any $\alpha \in \{1, 2, 3, 4\}$, $c$ can be extended to a good coloring of $G_{i, k}$ such that $c(v_{i+k-1}v_{i+k}) = \alpha$. □

Lemma 2.4. Let $G_{i, k}$ be a bottom block with $k\ge 1$. If $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is a crossing-edge, then $c$ cannot be extended to a good coloring of $G$.

Proof. First assume that $k = 1$, then $i = r-1$. If $v_{r-1}u_{r-1}$ is a crossing-edge, then $c(u_{r-1}u_r) = \overline{c}(v_{r-1})$ and $c(v_{r-1}v_r) = \overline{c}(u_{r-1})$. Hence statement (3) and (4) of Lemma 2.1 can not hold. Since $\overline{c}(u_{r-1})\neq c(u_{r-1}u_r)$, we have $c(u_{r-1}u_r)\neq c(v_{r-1}v_r)$. It follows that statement (1) and (2) of Lemma 2.1 can not hold. Therefore, by Lemma 2.1, $c$ cannot be extended to a good coloring of $G$.

Suppose $k\geq 2$. If $v_iu_i$ is a crossing-edge, then $c(u_iu_{i+1}) = \overline{c}(v_i)$ and $c(v_iv_{i+1}) = \overline{c}(u_i)$. Without loss of generality, assume that $c(u_iu_{i+1}) = \overline{c}(v_i) = 1$ and $c(v_iv_{i+1}) = \overline{c}(u_i) = 2$, then $u_{i+1}u_{i+1}''$ must be colored with $2$ and $v_{i+1}v_{i+2}$ must be colored with $1$. But then $S(u_{i+1}) = S(v_{i+1})$ no matter what color of $u_{i+1}v_{i+1}$ is, which shows that $c$ cannot be extended to a good coloring of $G$. □

Theorem 2.1. If $G$ is a necklace in $\mathcal{G}_r$ for $r\ge 2$, then $\chi'_{avd}(G) = 4$ if $r\notin \{4, 5\}$, otherwise $\chi'_{avd}(G) = 5$.

Proof. If $r = 2$, then $G$ is the graph depicted in Figure 4. Let $c(u_0v_1) = c(u_2v_2) = 1, \; c(u_0u_1) = c(v_2u_3) = 2, \; c(u_1v_1) = c(u_2u_3) = 3$, and $c(u_0u_3) = c(v_1v_2) = c(u_1u_2) = 4$. It is easy to check that $c$ is a good coloring of $G$.

Now we assume that $r\ge 3$. Note that $G$ is the union of end-graphs $G_1$, $G_r$, and a $(r-2)$-bottom block. We first give a good coloring of $G_1$. By Proposition 2.1, there are four types of colorings on $G_1$. In type (1) and (2), $c(u_1u_2) = c(v_1v_2)$, which means $u_2v_2$ is a crossing edge, by Lemma 2.4, this coloring cannot be extended to a good coloring of $G$.

In type (3), $c(u_1u_2) = c(u_0u_{r+1})$, $c(u_1u_2)\neq c(v_1v_2)$, $c(u_1u_2) = \overline{c}(v_1)$, and $c(u_0v_1) = \overline{c}(u_1)$. Since $c(u_0v_1)\neq c(v_1v_2)$, we have $c(v_1v_2)\neq \overline{c}(u_1)$, which means that $v_2u_2$ is an out-half-edge. By Lemma 2.2, $c$ can be extended to a good coloring of $G$ if and only if $c(u_0u_{r+1}) = c(v_{r-1}v_r)$.

If $r = 3$, then since $v_2u_2$ is an out-half-edge, $c(v_2v_3) = c(u_1u_2) = c(u_0u_4)$, hence $c$ can be extended to a good coloring of $G$.

If $r = 4$, then by Lemma 2.2, $v_3u_3$ is an out-half-edge, hence $c(v_3v_4) = c(u_2u_3)$. Since $c(u_2u_3)\neq c(u_1u_2)$, it follows that $c(u_0u_{r+1})\neq c(v_3v_4)$, hence $c$ cannot be extended to a good coloring of $G$.

If $r = 5$, then $c(v_4v_5) = c(u_3u_4)$ and $c(u_3u_4) = \overline{c}(v_3)$ since $v_4u_4$ is still an out-half-edge. Note that $\overline{c}(v_3)\neq c(v_2v_3)$ and $c(v_2v_3) = c(u_1u_2)$, it follows that $c(v_4v_5)\neq c(u_1u_2)$, that is, $c(u_0u_{r+1})\neq c(v_4v_5)$, hence $c$ cannot be extended to a good coloring of $G$.

If $r\ge 6$, then $r-2\ge 4$. By Lemma 2.3, let $\alpha = c(u_0u_{r+1})$, then $c$ can be extended to a good coloring of $G_{2, r-2}$ such that $c(v_{r-1}v_r) = c(u_0u_{r+1})$, hence $c$ can be extended to a good coloring of $G$.

By symmetry, if the coloring of $G_1$ is of type (4), then the edge $v_2u_2$ is an in-half-edge. By the same argument, we will obtain a good coloring of $G$ if $r\neq 4$ and $r\neq 5$.

In summary, if $r\notin \{4, 5\}$, we could obtained a good coloring of $G$, and for $r = 4$ or $r = 5$, $\chi'_{avd}(G)\ge 5$. Since $G$ is cubic, $\chi'_{avd}(G)\ge 4$, thus $\chi'_{avd}(G) = 4$ if $r\notin \{4, 5\}$. For $r = 4$ or $r = 5$, from Theorem 1.1, we have $\chi'_{avd}(G) = 5$. □

Lemma 2.5. Suppose $G_{i, k}$ is a bottom block, and $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is a full-edge. If $k = 1$ or $k\ge 3$, then $c$ can be extended to a good coloring of $G$. If $k = 2$, then $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1})$ is suitable.

Proof. Without loss of generality, let $c(v_{i-1}v_i) = 1, \; c(u_i'u_i) = 2, \; \overline{c}(v_{i-1}) = 3$ and $\overline{c}(u_i') = 4$. We will consider the following two cases.

Case 1. $k = 1$. Then $i = r-1$. Let $c(v_{r-1}v_r) = c(u_{r-1}u_r) = 3$, $c(v_{r-1}u_{r-1}) = 4$. If $c(u_{r-2}u_{r+1}) = 3$, then statement (1) of Lemma 2.1 holds. If $c(u_{r-2}u_{r+1})\neq 3$, we have $\overline{c}(u_{r-2})\neq c(u_{r-1}u_r)$ since $\overline{c}(u_{r-2})\neq \overline{c}(v_{r-2})$ and $\overline{c}(v_{r-2}) = 3$. Hence statement (2) of Lemma 2.1 holds. Therefore, we will obtain a good coloring of $G$ by Lemma 2.1.

Case 2. $k\ge 2$. Note that $\overline{c}(v_{i-1})$ must appear on the edges incident with $v_i$, that is, $v_iu_i$ or $v_iv_{i+1}$ is colored with $3$.

Subcase 2.1. $v_iu_i$ is colored with $3$. Then $u_iu_{i+1}$ is colored with 4. If $v_iv_{i+1}$ is colored with 4, then $v_{i+1}u_{i+1}$ is a crossing-edge, by Lemma 2.4, this coloring cannot be extended to a good coloring of $G$. Hence $v_iv_{i+1}$ is colored with 2. It follows that $\overline{c}(v_i) = 4$ and $\overline{c}(u_i) = 1$. Thus $v_{i+1}u_{i+1}$ is an out-half-edge. By Lemma 2.2, $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1}) = c(v_{r-1}v_r)$.

If $k = 2$, then $r = i+2$, $c(v_{r-1}v_r) = c(v_{i+1}v_{i+2})$. Since $c(v_{i+1}v_{i+2}) = c(u_iu_{i+1}) = 4$, $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1}) = 4 = \overline{c}(u_i')$.

If $k = 3$, then $r = i+3$. Denote $c(u_{i-1}u_{r+1}) = \alpha$. If $\alpha \in \{1, 3\}$, then let $c(v_{i+2}v_{i+3}) = c(u_{i+1}u_{i+2}) = \alpha$, $c(v_{i+1}v_{i+2}) = 4$, $c(v_{i+1}u_{i+1}) = \{1, 3\}\backslash \{\alpha\}$, $c(u_{i+2}v_{i+2})\in \{1, 2, 3\}\backslash \{\alpha\}$, $c(u_{i+2}u_r) = \{1, 2, 3\}\backslash \{\alpha, c(u_{i+2}v_{i+2})\}$. Now we obtain a good coloring of $G_{i, k}$ such that $c(u_{i-1}u_{r+1}) = c(v_{i+2}v_{i+3}) = c(v_{r-1}v_r)$.

If $k = 4$, then $r = i+4$. Denote $c(u_{i-1}u_{r+1}) = \alpha$. If $\alpha \in \{1, 2, 3\}$, then let $c(v_{i+1}v_{i+2}) = 4$, $c(v_{i+3}v_{i+4}) = c(u_{i+2}u_{i+3}) = \alpha$, $c(v_{i+2}v_{i+3}) = c(u_{i+1}u_{i+2})\in \{1, 3\}\backslash \{\alpha\}$, $c(u_{i+3}u_r)\in \{1, 2, 3, 4\}\backslash \{c(v_{i+2}v_{i+3}), \alpha\}$, $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_ju_{j+1})\}$ for $j = i+1, i+2, i+3$. Now we obtain a good coloring of $G_{i, k}$ such that $c(u_{i-1}u_{r+1}) = c(v_{i+3}v_{i+4}) = c(v_{r-1}v_r)$.

If $k\ge 5$, by Lemma 2.3, let $\alpha = c(u_{i-1}u_{r+1})$, then we can obtain a good coloring of $G_{i, k}$ such that $c(v_{r-1}v_r) = \alpha = c(u_{i-1}u_{r+1})$.

Subcase 2.2. $v_iv_{i+1}$ is colored with $3$. If $u_iu_{i+1}$ is colored with 4, then the edge $v_iu_i$ cannot be colored to obtain a good coloring. Hence $v_iu_i$ is colored with 4. If $u_iu_{i+1}$ is colored with 3, then $v_{i+1}u_{i+1}$ is a crossing-edge, by Lemma 2.4, this coloring cannot be extended to a good coloring of $G$. Hence $u_iu_{i+1}$ is colored with 1. It follows that $\overline{c}(v_i) = 2$ and $\overline{c}(u_i) = 3$. Thus $v_{i+1}u_{i+1}$ is an in-half-edge. By Lemma 2.2, $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1}) = c(u_{r-1}u_r)$.

If $k = 2$, then $r = i+2$, $c(u_{r-1}u_r) = c(u_{i+1}u_{i+2})$. Since $c(u_{i+1}u_{i+2}) = c(v_iv_{i+1}) = 3$, $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1}) = 3 = \overline{c}(v_{i-1})$.

If $k = 3$, then $r = i+3$. Denote $c(u_{i-1}u_{r+1}) = \alpha$. If $\alpha \in \{2, 4\}$, then let $c(u_{i+2}u_{i+3}) = c(v_{i+1}v_{i+2}) = \alpha$, $c(u_{i+1}u_{i+2}) = 3$, $c(v_{i+1}u_{i+1}) = \{2, 4\}\backslash \{\alpha\}$, $c(u_{i+2}v_{i+2})\in \{1, 2, 4\}\backslash \{\alpha\}, \; c(v_{i+2}v_r) = \{1, 2, 4\}\backslash \{\alpha, c(u_{i+2}v_{i+2})\}$. Now we obtain a good coloring of $G_{i, k}$ such that $c(u_{i-1}u_{r+1}) = c(u_{i+2}u_{i+3}) = c(u_{r-1}u_r)$.

If $k = 4$, then $r = i+4$. Denote $c(u_{i-1}u_{r+1}) = \alpha$. If $\alpha \in \{1, 2, 4\}$, then let $c(u_{i+1}u_{i+2}) = 3$, $c(u_{i+3}u_{i+4}) = c(v_{i+2}v_{i+3}) = \alpha$, $c(u_{i+2}u_{i+3}) = c(v_{i+1}v_{i+2})\in \{2, 4\}\backslash \{\alpha\}$, $c(v_{i+3}v_r)\in \{1, 2, 3, 4\}\backslash \{c(u_{i+2}u_{i+3}), \alpha\}$, $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(u_{j-1}u_j), c(u_ju_{j+1}), c(v_jv_{j+1})\}$ for $j = i+1, i+2, i+3$. Now we obtain a good coloring of $G_{i, k}$ such that $c(u_{i-1}u_{r+1}) = c(u_{i+3}u_{i+4}) = c(u_{r-1}u_r)$.

If $k\ge 5$, by Lemma 2.3, let $\alpha = c(u_{i-1}u_{r+1})$, then we can obtain a good coloring of $G_{i, k}$ such that $c(u_{r-1}u_r) = \alpha = c(u_{i-1}u_{r+1})$.

Combining Subcase 2.1 and Subcase 2.2, for $k\ge 3$, we can obtain a good coloring of $G$. But for $k = 2$, $c$ can be extended to a good coloring of $G$ if and only if $c(u_{i-1}u_{r+1})\in \{\overline{c}(u_i'), \overline{c}(v_{i-1})\}$, that is $c(u_{i-1}u_{r+1})$ is suitable. □

Lemma 2.6. Let $G_{i, k, c}$ be a $k$-crossing block. Suppose the associated subgraph $H_{i, k, c}$ has a good coloring $c$ such that $v_iu_i$ is a full-edge.

(1) If $v_{i-1}u_{i-1}$ is an outer-crossing-edge, then $c$ can be extended to a good coloring of $G_{i, k, c}$ such that for each $j$, $i+1\le j\le i+k$, $v_ju_j$ is a full-edge and $v_{j-1}u_{j-1}$ is an outer-crossing-edge.

(2) If $v_{i-1}u_{i-1}$ is a crossing-edge, then for each $j$, $i+1\le j\le i+k$, we can extend $c$ such that $v_ju_j$ is a full-edge and $c(u_{j-1}u_{j-1}'') = \overline{c}(v_{j-1})$.

Proof. Without loss of generality, assume that $c(v_{i-1}v_i) = 1, \; c(u_i'u_i) = 2, \; \overline{c}(v_{i-1}) = 3$ and $\overline{c}(u_i') = 4$.

Considering the case that $v_{i-1}u_{i-1}$ is an outer-crossing-edge, that is, $c(v_{i-1}v_i) = \overline{c}(u_{i-1})$ and $c(u_{i-1}u_{i+1}) = \overline{c}(u_i')$. So $\overline{c}(u_{i-1}) = 1, \; c(u_{i-1}u_{i+1}) = 4$. We set $c(v_iv_{i+1}) = 3, \; c(u_iu_i'') = 1$, and $c(v_iu_i) = 4$. Then $\overline{c}(v_i) = 2$ and $\overline{c}(u_i) = 3$. Hence, the edge $v_{i+1}u_{i+1}$ is a full-edge, and $v_iu_i$ is an outer-crossing-edge. Note that the edge $v_{i+1}u_{i+1}$ has the same property as $v_iu_i$, then we can do the similar coloring such that for each $j$, $i+1\le j\le i+k$, $v_ju_j$ is a full-edge and $v_{j-1}u_{j-1}$ is an outer-crossing-edge.

Considering the case that $v_{i-1}u_{i-1}$ is a crossing-edge, that is, $c(v_{i-1}v_i) = \overline{c}(u_{i-1})$ and $c(u_{i-1}u_{i+1}) = \overline{c}(v_{i-1})$. So $\overline{c}(u_{i-1}) = 1, c(u_{i-1}u_{i+1}) = 3$. If $k = 1$, we set $c(v_iv_{i+1}) = 2, c(u_iu_i'') = 4$, and $c(v_iu_i) = \; 3$. Then $\overline{c}(v_i) = 4$ and $\overline{c}(u_i) = 1$. Hence, the edge $v_{i+1}u_{i+1}$ is a full-edge, and $c(u_iu_i'') = \overline{c}(v_i)$. If $k\ge 2$, then we reset the coloring such that $c(v_{i+1}u_{i+1}) = 1$, $c(v_{i+1}v_{i+2}) = 2$, $c(v_iv_{i+1}) = c(u_iu_{i+2}) = 3$, $c(v_iu_i) = c(u_{i+1}u_{i+1}'') = 4$. Then $\overline{c}(v_{i+1}) = 4$, $\overline{c}(u_{i+1}) = 2$, and $\overline{c}(u_i) = 1$. Hence, the edge $v_{i+2}u_{i+2}$ is a full-edge, and $v_{i+1}u_{i+1}$ is a crossing-edge, which shows that $c(u_{i+1}u_{i+1}'') = \overline{c}(v_{i+1})$. Note that the edge $v_{i+2}u_{i+2}$ has the same property as $v_iu_i$, then we can do the similar coloring such that $v_ju_j$ is a full-edge and $c(u_{j-1}u_{j-1}'') = \overline{c}(v_{j-1})$ for $i+1\le j\le i+k$. □

Lemma 2.7. Let $G_{i, k}$ be a $k$-block with $k\ge 2$. Suppose $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is a full-edge, then

(1) If $G_{i, k}$ is adjacent to a $t$-block $G_{i+k, t}$, then we can extend the coloring $c$ such that $v_{i+k}u_{i+k}$ is a full-edge. Moreover, if $c(u_{i+k-1}u_{i+k-1}'')$ is not suitable and the $G_{i+k, t}$ is a bottom block with $t = 2$, then $c$ can be extended to a good coloring of $G$.

(2) If $G_{i, k}$ is adjacent to a $t$-crossing block $G_{i+k, t, c}$ with $t\ge 2$, then we can extend the coloring $c$ such that $v_{i+k+t-1}u_{i+k+t-1}$ is a full-edge and $c(u_{i+k+t-2}u_{i+k+t-2}'')$ is suitable.

Proof. Without loss of generality, suppose $c(v_{i-1}v_i) = 1, \; c(u_i'u_i) = 2, \overline{c}(v_{i-1}) = 3$ and $\overline{c}(u_i') = 4$. Then we have $\overline{c}(u_{i-1})\neq 3$. If $c(u_{i-1}u_{i-1}'') = 2$ and $\overline{c}(u_{i-1}) = 4$, then $c(v_{i-2}v_{i-1}) = 4$ and $c(u_{i-1}'u_{i-1}) = 3$, it follows that the edge $v_{i-1}u_{i-1}$ cannot be AVD-edge-colored with 4 colors. Similarly for the case $c(u_{i-1}u_{i-1}'') = 4$ and $\overline{c}(u_{i-1}) = 2$. Hence, we have $\langle c(u_{i-1}u_{i-1}''), \overline{c}(u_{i-1}) \rangle \in \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 4 \rangle, \langle 4, 1 \rangle, \langle 3, 1 \rangle, \langle 3, 2 \rangle, \langle 3, 4 \rangle\}$, where $\langle a, b \rangle$ is an ordered pair and $\langle a, b \rangle = \langle c, d \rangle$ if and only if $a = c$ and $b = d$.

Now we divide the proof into the following three cases depending on $k$.

Case 1. $k = 2$. Then $u_{i-1}'' = u_{i+2}$.

Subcase 1.1. $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle \in \{\langle 1, 2 \rangle, \langle 2, 1 \rangle\}$.

First considering the case that $G_{i, 2}$ is adjacent to a $t$-block. Set $c(v_{i+1}u_{i+1}) = 1, c(v_iv_{i+1}) = 2$, $c(v_iu_i) = c(u_{i+1}u_{i+1}'') = 3, \; c(u_iu_{i+1}) = c(v_{i+1}v_{i+2}) = 4$, then $\overline{c}(v_{i+1}) = 3$ and $c(u_{i+1}u_{i+1}'') = \overline{c}(v_{i+1})$. It is easy to see that $v_{i+2}u_{i+2}$ is a full-edge and $c(u_{i+1}u_{i+1}'')$ is suitable.

Now considering the case that $G_{i, 2}$ is adjacent to a $t$-crossing block. Set $c(v_{i+1}u_{i+1}) = \; 1, c(v_{i+1}v_{i+2}) = \; 2$, $c(v_iu_i) = c(u_{i+1}u_{i+1}'') = c(v_{i+2}u_{i+2}) = 3, \; c(v_iv_{i+1}) = c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = 4$. If $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle = \langle 1, 2 \rangle$, then set $c(u_{i+2}u_{i+2}'') = 2$. It is easy to see that $v_{i+3}u_{i+3}$ is a full-edge and $v_{i+2}u_{i+2}$ is an outer-crossing-edge. If $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle = \langle 2, 1 \rangle$, then set $c(u_{i+2}u_{i+2}'') = 1$. It follows that $v_{i+3}u_{i+3}$ is a full-edge and $v_{i+2}u_{i+2}$ is a crossing-edge. By Lemma 2.6, we can extend the coloring $c$ such that $v_{i+2+t-1}u_{i+2+t-1}$ is a full-edge and $c(u_{i+2+t-2}u_{i+2+t-2}'')$ is suitable.

Subcase 1.2. $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle \in \{\langle 1, 4 \rangle, \langle 4, 1 \rangle\}$.

In this case, set $c(v_{i+1}u_{i+1}) = 1, \; c(u_{i+1}u_{i+1}'') = 2$, $c(v_iu_i) = c(v_{i+1}v_{i+2}) = 3, \; c(v_iv_{i+1}) = c(u_iu_{i+1}) = 4$. Then $\overline{c}(v_{i+1}) = 2$, $v_{i+2}u_{i+2}$ is a full-edge and $v_{i+1}u_{i+1}$ is a crossing-edge. Hence, if $G_{i, 2}$ is adjacent to a $t$-block, then we have shown that $v_{i+2}u_{i+2}$ is a full-edge and $c(u_{i+1}u_{i+1}'')$ is suitable. If $G_{i, 2}$ is adjacent to a $t$-crossing block, then by Lemma 2.6, we can extend the coloring $c$ such that $v_{i+2+t-1}u_{i+2+t-1}$ is a full-edge and $c(u_{i+2+t-2}u_{i+2+t-2}'')$ is suitable.

Subcase 1.3. $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle \in \{\langle 3, 1 \rangle, \langle3, 2 \rangle, \langle3, 4 \rangle\}$.

First set $c(v_iu_i) = 4, c(v_iv_{i+1}) = c(u_iu_{i+1}) = 3$. If $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle = \langle 3, 1 \rangle$, then set $c(v_{i+1}u_{i+1}) = \; 1, \; c(v_{i+1}v_{i+2}) = 2, \; c(u_{i+1}u_{i+1}'') = 4$. If $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle = \langle 3, 2 \rangle$, then set $c(v_{i+1}u_{i+1}) = 2, \; c(v_{i+1}v_{i+2}) = 4, \; c(u_{i+1}u_{i+1}'') = 1$. If $\langle c(u_{i-1}u_{i+2}), \overline{c}(u_{i-1}) \rangle = \langle3, 4 \rangle$, then set $c(v_{i+1}u_{i+1}) = \; 4, \; c(v_{i+1}v_{i+2}) = 2, \; c(u_{i+1}u_{i+1}'') = 1$. In all these cases, we have that $v_{i+2}u_{i+2}$ is a full-edge and $v_{i+1}u_{i+1}$ is a crossing-edge. Therefore, the conclusion holds for these subcases.

Case 2. $k = 3$. Then $u_{i-1}'' = u_{i+3}$.

Subcase 2.1. $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle \in \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 4 \rangle, \langle 4, 1 \rangle\}$.

First considering that $G_{i, 3}$ is adjacent to a $t$-block. If $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle \in \{\langle 1, 2 \rangle, \langle 2, 1 \rangle\}$, then set $c(u_iu_{i+1}) = c(v_{i+2}u_{i+2}) = 1, \; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+2}'') = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = \; 3, \; c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = 4$, denote this coloring as (A). Under this coloring, we have $\langle c(v_{i+2}v_{i+3}), \overline{c}(v_{i+2}) \rangle = \langle 4, 3 \rangle$, hence $v_{i+3}u_{i+3}$ is a full-edge. Note that if $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 1, 2 \rangle$, then $c(u_{i+2}u_{i+2}'')$ is suitable, and $v_{i+2}u_{i+2}$ is an outer-crossing-edge. But if $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 2, 1 \rangle$, then $c(u_{i+2}u_{i+2}'')$ is not suitable. For this case, if $G_{i+3, t}$ is a bottom block with $t = 2$, see Figure 5, then we color the edges of $G_{i, 3}\cup G_{i+3, 2}\cup G_r$ as follows: $c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = c(v_{i+5}u_{i+6}) = 1$, $c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+4}v_{i+5}) = c(u_{i+5}u_{i+6}) = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}u_{i+4}) = c(v_{i+5}u_{i+5}) = 3$, $c(v_iu_i) = c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+6}) = c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+5}) = 4$. It follows that $c$ is a good coloring of $G$.

If $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1})\rangle\in \{\langle 1, 4\rangle, \langle 4, 1 \rangle\}$, then set $c(u_iu_{i+1}) = c(v_{i+2}u_{i+2}) = 1, \; c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = 2,$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 3, \; c(v_iu_i) = \; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+2}'') = 4$, denote this coloring as (B). Under this coloring, we have $\langle c(v_{i+2}v_{i+3}), \overline{c}(v_{i+2}) \rangle = \langle 2, 3 \rangle$, hence $v_{i+3}u_{i+3}$ is a full-edge. Similarly, if $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 1, 4 \rangle$, then $c(u_{i+2}u_{i+2}'')$ is suitable, and $v_{i+2}u_{i+2}$ is an outer-crossing-edge. But if $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, then $c(u_{i+2}u_{i+2}'')$ is not suitable. For this case, if $G_{i+3, t}$ is a bottom block with $t = 2$, see Figure 6, then we color the edges of $G_{i, 3}\cup G_{i+3, 2}\cup G_r$ as follows: $c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = c(v_{i+5}u_{i+6}) = 1$, $c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+6}) = c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+5}) = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}u_{i+4}) = c(v_{i+5}u_{i+5}) = 3$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+4}v_{i+5}) = c(u_{i+5}u_{i+6}) = 4$. It follows that $c$ is a good coloring of $G$.

Now considering the case that $G_{i, 3}$ is adjacent to a $t$-crossing block. If $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 1, 2 \rangle$, then we use coloring (A), under this coloring, $v_{i+3}u_{i+3}$ is a full-edge and $v_{i+2}u_{i+2}$ is an outer-crossing-edge, by Lemma 2.6, we can extend the coloring $c$ such that $v_{i+3+t-1}u_{i+3+t-1}$ is a full-edge and $c(u_{i+3+t-2}u_{i+3+t-2}'')$ is suitable. Similarly, if $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 1, 4 \rangle$, then we use coloring (B), and extend this coloring to the $t$-crossing block such that $v_{i+3+t-1}u_{i+3+t-1}$ is a full-edge and $c(u_{i+3+t-2}u_{i+3+t-2}'')$ is suitable.

For the case $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 2, 1 \rangle$, we first use coloring (B), and then set $c(v_{i+3}u_{i+3}) = \; 4, \; c(u_{i+3}u_{i+3}'') = 1$, and $c(v_{i+3}v_{i+4}) = 3$, then $\overline{c}(v_{i+3}) = 1, \; \overline{c}(u_{i+3}) = 3$, so $v_{i+3}u_{i+3}$ is a crossing-edge. Note that $v_{i+4}u_{i+4}$ is a full-edge. By Lemma 2.6, we can extend the coloring $c$ such that $v_{i+3+t-1}u_{i+3+t-1}$ is a full-edge and $c(u_{i+3+t-2}u_{i+3+t-2}'')$ is suitable. Similarly, for the case $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, we first use coloring (A), and then set $c(v_{i+3}u_{i+3}) = 2, \; c(u_{i+3}u_{i+3}'') = 1$, and $c(v_{i+3}v_{i+4}) = 3$, which makes $v_{i+3}u_{i+3}$ a crossing-edge and $v_{i+4}u_{i+4}$ a full-edge. By Lemma 2.6, the conclusion holds for this case.

Subcase 2.2. $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 3, 4 \rangle$.

Considering that $G_{i, 3}$ is adjacent to a $t$-block. Set $c(u_{i+1}u_{i+2}) = c(v_{i+2}v_{i+3}) = 1, \; c(v_iv_{i+1}) = c(u_{i+2}u_{i+2}'') = 2$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = 3, \; c(u_iu_{i+1}) = c(v_{i+1}v_{i+2}) = 4$, denote this coloring as (C). Then $\langle c(v_{i+2}v_{i+3}), \overline{c}(v_{i+2}) \rangle = \langle 1, 2 \rangle$, hence $v_{i+3}u_{i+3}$ is a full-edge and $c(u_{i+2}u_{i+2}'')$ is suitable.

Considering the case that $G_{i, k}$ is adjacent to a $t$-crossing block. If $t = 2$, then let $c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = 1, \; c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(u_{i+3}u_{i+3}'') = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}v_{i+4}) = \; 3, \; c(v_iu_i) = c(v_{i+1}v_{i+2}) = c(v_{i+3}u_{i+3}) = c(u_{i+2}u_{i+2}'') = 4$. Then $v_{i+4}u_{i+4}$ becomes a full-edge and $c(u_{i+3}u_{i+3}'')$ is suitable. If $t\ge 3$, then we first use coloring (C), then set $c(v_{i+4}u_{i+4}) = c(u_{i+3}u_{i+5}) = \; 1, \; c(v_{i+3}v_{i+4}) = 2$, $c(v_{i+4}v_{i+5}) = 3, \; c(v_{i+3}u_{i+3}) = c(u_{i+4}u_{i+4}'') = 4$. It is easy to see that $v_{i+5}u_{i+5}$ is a full-edge and $v_{i+4}u_{i+4}$ is a crossing-edge. By Lemma 2.6, we can extend the coloring $c$ such that $v_{i+3+t}u_{i+3+t}$ is a full-edge and $c(u_{i+3+t-1}u_{i+3+t-1}'')$ is suitable.

Subcase 2.3. $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 3, 2 \rangle$.

Since $\overline{c}(u_{i-1}) = 2$ and $\overline{c}(v_{i-1}) = 3$, we have $c(v_{i-2}v_{i-1}) = 2$ and $c(v_{i-1}u_{i-1}) = 4$. If $\overline{c}(v_{i-2})\neq 4$, then we transform $c(u_{i-1}u_{i+3})$ from 3 to 4 and $c(u_{i-1}v_{i-1})$ from 4 to 3, which changes $\overline{c}(v_{i-1})$ from 3 to 4. Set $c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = 1, \; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+2}'') = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 3, \; c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = 4$. Then $v_{i+3}u_{i+3}$ becomes a full-edge and $v_{i+2}u_{i+2}$ becomes an outer-crossing-edge. If $\overline{c}(v_{i-1}) = 4$, then we transform $c(v_{i-1}v_i)$ from 1 to 3, which changes $\overline{c}(v_i)$ from 3 to 1. Note that $v_iu_i$ is still a full-edge, we exchange the color 1 and 3 in coloring (A), it follows that $v_{i+3}u_{i+3}$ becomes a full-edge and $v_{i+2}u_{i+2}$ becomes an outer-crossing-edge. Hence the conclusion holds for this subcase.

Subcase 2.4. $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 3, 1 \rangle$.

In this case, $c(v_{i-1}u_{i-1})\in \{2, 4\}$.

Subcase 2.4.1. $c(v_{i-1}u_{i-1}) = 4$. Then $c(u_{i-1}'u_{i-1}) = c(v_{i-2}v_{i-1}) = 2$.

We only need to consider the case that at least one of $\overline{c}(u_{i-1}')$ and $\overline{c}(v_{i-2})$ is distinct with 4. Otherwise, if $\overline{c}(u_{i-1}') = \overline{c}(v_{i-2}) = 4$, then $v_{i-2}u_{i-1}'\notin E(G)$, hence $v_{i-2}u_i'\in E(G)$, but $\overline{c}(u_i') = 4$, which is impossible.

Subcase 2.4.1.1. $\overline{c}(u_{i-1}')\neq 4$.

Consider the coloring $c$ on $H_{i, 3}$, we transform $c(v_{i-1}u_{i-1})$ from 4 to 1 and $c(v_{i-1}v_i)$ from 1 to 4, then $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 3, 4 \rangle$, $\langle c(v_{i-1}v_i), \overline{c}(v_{i-1}) \rangle = \langle 4, 3 \rangle$. If $G_{i, 3}$ is adjacent to a $t$-block, then set $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 1, \; c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = 2$, $c(v_iu_i) = c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+2}'') = \; 3, \; c(u_iu_{i+1}) = c(v_{i+2}u_{i+2}) = 4$. Then $v_{i+3}u_{i+3}$ becomes a full-edge, but $c(u_{i+2}u_{i+2}'')$ is not suitable. For this case, if $G_{i+3, t}$ is a bottom block with $t = 2$, then we color the edges of $G_{i, 3}\cup G_{i+3, 2}\cup G_r$ as follows: $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+4}u_{i+5}) = c(v_{i+5}u_{i+6}) = 1$, $c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+6}) = c(u_{i+3}u_{i+4}) = c(v_{i+4}v_{i+5}) = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}v_{i+4}) = c(u_{i+5}u_{i+6}) = 3$, $c(u_iu_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}u_{i+4}) = c(v_{i+5}u_{i+5}) = 4$. Then $c$ is a good coloring of $G$.

If $G_{i, 3}$ is adjacent to a $t$-crossing block, then set $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}v_{i+4}) = 1, \; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+4}) = c(v_{i+3}u_{i+3}) = 2$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = 3, \; c(v_{i+2}u_{i+2}) = c(u_{i+3}u_{i+3}'') = 4$. Then $v_{i+4}u_{i+4}$ becomes a full-edge and $v_{i+3}u_{i+3}$ becomes a crossing-edge. By Lemma 2.6, we can extending the coloring $c$ such that $v_{i+3+t-1}u_{i+3+t-1}$ is a full-edge and $c(u_{i+3+t-2}u_{i+3+t-2}'')$ is suitable.

Subcase 2.4.1.2. $\overline{c}(v_{i-2})\neq 4$.

Consider the coloring $c$ on $H_{i, 3}$, we transform $c(u_{i-1}u_{i+3})$ from 3 to 4 and $c(v_{i-1}u_{i-1})$ from 4 to 3, then $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, $\langle c(v_{i-1}v_i), \overline{c}(v_{i-1}) \rangle = \langle 1, 4 \rangle$. If $G_{i, 3}$ is adjacent to a $t$-block, then we use coloring (B) on $G_{i, k}$, under this coloring, $v_{i+3}u_{i+3}$ is a full-edge, but $c(u_{i+2}u_{i+2}'')$ is not suitable. For this case, if $G_{i+3, t}$ is a bottom block with $t = 2$, then we give a coloring on the edges of $G_{i, 3}\cup G_{i+3, 2}\cup G_r$ as follows: $c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = c(v_{i+5}u_{i+6}) = 1$, $c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+6}) = c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+5}) = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}v_{i+5}) = c(u_{i+5}u_{i+6}) = 3$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+4}u_{i+4}) = c(v_{i+5}u_{i+5}) = 4$. Then $c$ is a good coloring of $G$.

If $G_{i, 3}$ is adjacent to a $t$-crossing block with $t\ge 2$, then we use coloring (A) on $G_{i, 3}$, and set $c(u_{i+3}u_{i+3}'') = 1, \; c(v_{i+3}u_{i+3}) = 2$, $c(v_{i+3}v_{i+4}) = 3$. It is easy to see that $v_{i+4}u_{i+4}$ is a full-edge and $v_{i+3}u_{i+3}$ becomes a crossing-edge. Hence the conclusion holds for this subcase.

Subcase 2.4.2. $c(v_{i-1}u_{i-1}) = 2$. Then $c(u_{i-1}'u_{i-1}) = c(v_{i-2}v_{i-1}) = 4$.

We divide the proof of this case into the following two parts depending on which side $u_{i-2}$ is on.

Subcase 2.4.2.1. $u_{i-2}$ and $u_{i-1}$ are on the same side of $P$, that is, $u_{i-1}' = u_{i-2}$.

Since $c(u_{i-1}'u_{i-1}) = c(v_{i-2}v_{i-1}) = 4$, we have $c(v_{i-2}u_{i-2})\in \{1, 2, 3\}$.

If $c(v_{i-2}u_{i-2}) = 1$, then under the coloring $c$ on $H_{i, 3}$, we transform $c(v_{i-2}u_{i-2}), \; c(v_{i-1}v_i)$ from 1 to 4, and $c(u_{i-2}u_{i-1}), \; c(v_{i-2}v_{i-1})$ from 4 to 1. Note that $c$ is still a good coloring of $H_{i, k}$, and $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 3, 4 \rangle$, $\langle c(v_{i-1}v_i), \overline{c}(v_{i-1}) \rangle = \langle 4, 3 \rangle$. We then use the same coloring with subcase 2.4.1.1.

If $c(v_{i-2}u_{i-2}) = 2$, then consider the coloring $c$ on $H_{i, k}$, we transform $c(v_{i-2}u_{i-2}), \; c(v_{i-1}u_{i-1})$ from 2 to 4, and $c(u_{i-2}u_{i-1}), \; c(v_{j-2}v_{j-1})$ from 4 to 2, then $c$ is still a good coloring of $H_{i, k}$, and it is the subcase 2.4.1.

If $c(v_{i-2}u_{i-2}) = 3$, then under the coloring $c$ on $H_{i, k}$, we transform $c(v_{i-2}u_{i-2}), \; c(u_{i-1}u_{i-1}'')$ from 3 to 4, and $c(u_{i-2}u_{i-1}), \; c(v_{i-2}v_{i-1})$ from 4 to 3, then $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, $\langle c(v_{i-1}v_i), \overline{c}(v_{i-1}) \rangle = \langle 1, 4 \rangle$. We then use the same coloring with subcase 2.4.1.2.

Subcase 2.4.2.2. $u_{i-2}$ and $u_i$ are on the same side of $P$, that is, $u_i' = u_{i-2}$.

Since $\overline{c}(u_{i-2}) = 4$ and $c(u_{i-2}u_i) = 2$, we have $c(v_{i-2}u_{i-2})\in \{1, 3\}$.

Considering the case that $c(v_{i-2}u_{i-2}) = 1$, then $c(u_{i-2}'u_{i-2}) = 3$. We also have $c(v_{i-3}v_{i-2}) = 3$ since $\overline{c}(v_{i-1}) = 3$. We may assume that $\overline{c}(u_{i-2}') = 1$. Otherwise if $\overline{c}(u_{i-2}')\neq 1$, then we transform $c(v_{i-1}v_i), \; c(v_{i-2}u_{i-2})$ from 1 to 4, and $c(v_{i-2}v_{i-1})$ from 4 to 1, which changes $\overline{c}(u_{i-2})$ from 4 to 1. We turn to subcase 2.2, and exchange the color 1 and 4 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring. Consider $\overline{c}(v_{i-3})$, it cannot equal to $c(v_{i-3}v_{i-2})$ and $\overline{c}(v_{i-2})$, hence $\overline{c}(v_{i-3})\in \{1, 4\}$.

If $\overline{c}(v_{i-3}) = 1$, then $u_{i-3} = u_{i-1}'$. Since $\overline{c}(u_{i-1}) = \overline{c}(v_{i-3}) = 1$ and $c(v_{i-3}v_{i-2}) = 3$, we have $c(u_{i-3}'u_{i-3}) = \; 1$, $c(v_{i-3}u_{i-3}) = 2$ and $c(v_{i-4}v_{i-3}) = 4$. If $\overline{c}(u_{i-3}')\neq 4$, then we transform $c(u_{i-3}u_{i-1})$ from 4 to 3, and transform $c(u_{i-1}u_{i+3})$ from 3 to 4, which can turn to subcase 2.1 for the case $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$. If $\overline{c}(u_{i-3}') = 4$, then we transform $c(v_{i-3}u_{i-3}), \; c(v_{i-1}u_{i-1})$ from 2 to 3, $c(v_{i-3}v_{i-2}), \; c(u_{i-1}u_{i+3})$ from 3 to 2, and transform $c(u_{i-2}u_i)$ from $4$ to $2$, then $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 2, 1 \rangle$, $\langle c(v_{i-1}v_i), \overline{c}(v_{i-1}) \rangle = \langle 1, 2 \rangle$. We exchage the color 2 and 3 in the subcase 2.4.1 for the case $\overline{c}(v_{i-2})\neq 4$.

If $\overline{c}(v_{i-3}) = 4$, consider $\overline{c}(u_{i-1}')$, it cannot equal to $c(u_{i-1}'u_{i-1})$ and $\overline{c}(u_{i-1})$, hence $\overline{c}(u_{i-1}')\in \{2, 3\}$. If $\overline{c}(u_{i-1}') = 2$, then we transform $c(v_{i-1}u_{i-1}), \; c(u_{i-2}u_i)$ from 2 to 1, $c(v_{i-1}v_i)$ from 1 to 3, $c(u_{i-1}u_{i+3})$ from 3 to 2, $c(v_{i-2}v_{i-1})$ from 4 to 2, $c(v_{i-2}u_{i-2})$ from 1 to 4, then we have $\overline{c}(u_{i-1}) = 3$, $\overline{c}(v_{i-1}) = 4$ and $\overline{c}(u_{i-2}) = 2$. We turn to subcase 2.1 when $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, and replace the color 1 to 3, 3 to 4, 4 to 2, and 2 to 1 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring. If $\overline{c}(u_{i-1}') = 3$, then we transform $c(v_{i-1}u_{i-1}), \; c(u_{i-2}u_i)$ from 2 to 1, $c(v_{i-2}u_{i-2}), \; c(v_{i-1}v_i)$ from 1 to 4, $c(v_{i-2}v_{i-1})$ from 4 to 2. We turn to subcase 2.2, replace the color 1 to 4, 4 to 2, and 2 to 1 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring.

Now we consider the case that $c(v_{i-2}u_{i-2}) = 3$. Since $\overline{c}(u_{i-2}) = 4$, we have $c(u_{i-2}'u_{i-2}) = 1$. Note that $c(v_{i-3}v_{i-2})\in \{1, 2\}$. For the case $c(v_{i-3}v_{i-2}) = 1$, consider $\overline{c}(u_{i-2}')$, we may assume $\overline{c}(u_{i-2}') = 3$. Otherwise, if $\overline{c}(u_{i-2}')\neq 3$, then we transform $c(v_{i-2}u_{i-2})$ from 3 to 4, and transform $c(v_{i-2}v_{i-1})$ from 4 to 3, it follows that $\overline{c}(v_{i-1}) = 4$ and $\overline{c}(u_{i-2}) = 3$. We turn to subcase 2.1 when $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, and exchange the color 3 and 4 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring. Now consider $\overline{c}(v_{i-3})$, it can be 3 or 4. If $\overline{c}(v_{i-3}) = 3$, then $u_{i-3} = u_{i-1}'$, and $c(u_{i-3}'u_{i-3}) = 3$. But since $\overline{c}(u_{i-1}) = 1$ and $c(v_{i-3}v_{i-2}) = 1$, it implies that $c(u_{i-3}'u_{i-3}) = 1$, a contradiction. Hence $\overline{c}(v_{i-3})\neq 3$, then $\overline{c}(v_{i-3}) = 4$. In this case, we transform $c(v_{i-1}u_{i-1}), \; c(u_{i-2}u_i)$ from 2 to 3, $c(v_{i-2}u_{i-2})$ from 3 to 4, $c(u_{i-1}u_{i+3})$ from 3 to 2, and $c(v_{i-2}v_{i-1})$ from 4 to 2. We turn to subcase 2.1 when $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, and replace the color 2 to 3, 3 to 4, 4 to 2 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring.

For the case $c(v_{i-3}v_{i-2}) = 2$, consider $\overline{c}(u_{i-2}')$, it can be 2 or 3. If $\overline{c}(u_{i-2}') = 2$, then we transform $c(v_{i-2}v_{i-1})$ from 4 to 3, and transform $c(v_{i-2}u_{i-2})$ from 3 to 4, then turn to subcase 2.1 when $\langle c(u_{i-1}u_{i+3}), \overline{c}(u_{i-1}) \rangle = \langle 4, 1 \rangle$, and exchange the color 3 and 4 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring. If $\overline{c}(u_{i-2}') = 3$, then we transform $c(u_{i-2}u_i)$ from 2 to 4, $c(v_{i-1}u_{i-1})$ from 2 to 3, $c(u_{i-1}u_{i+3})$ from 3 to 2, and turn to subcase 2.4.1.2, exchange the color 2 and 4 in the coloring of $G_{i, k}$ or $G_{i, k}\cup G_{i+k, t, c}$, then we obtain the desired coloring.

Case 3. $k\ge 4$.

Let $\langle c(u_{i-1}u_{i-1}''), \overline{c}(u_{i-1}) \rangle = \langle \alpha, \beta \rangle$, and $\langle \alpha, \beta \rangle$ be an ordered pair in $\{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 4 \rangle, \langle 4, 1 \rangle,$ $\langle 3, 1 \rangle, \langle 3, 2 \rangle, \langle 3, 4 \rangle\}$.

Subcase 3.1. $k = 4$.

Let $\gamma$ be a color in $\{2, 4\}\backslash \{\alpha, \beta\}$, $\delta = \{1, 2, 3, 4\}\backslash \{\alpha, \beta, \gamma\}$. Set $c(v_iu_i) = 4, \; c(u_iu_{i+1}) = 1, \; c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 3$, $\; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+3}) = \gamma, \; c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+3}'') = \beta,$ $c(v_{i+3}v_{i+4}) = \delta$. For $i+1 \le j\le i+3$, let $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_{j-1}u_j)\}$. Then, $v_{i+4}u_{i+4}$ is a full-edge and $v_{i+3}u_{i+3}$ is an outer-crossing-edge. Hence, if $G_{i, k}$ is adjacent to a $t$-block, then $v_{i+k}u_{i+k}$ is a full-edge and $c(u_{i+k-1}u_{i+k-1}'')$ is suitable. If $G_{i, k}$ is adjacent to a $t$-crossing block with $t\ge 2$, by Lemma 2.6, we can extend the coloring $c$ such that $v_{i+k+t-1}u_{i+k+t-1}$ is a full-edge and $c(u_{i+k+t-2}u_{i+k+t-2}'')$ is suitable.

Subcase 3.2. $k = 5$.

If $\alpha \neq 1$ and $\beta \neq 1$, then set $c(v_iu_i) = 4, \; c(u_iu_{i+1}) = 1, \; c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 3$, $\; c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = 1, \; c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+4}'') = \beta,$ $\; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+3})\in \{2, 4\}\backslash \{\beta\}$, $c(v_{i+4}v_{i+5})\in \{1, 2, 3, 4\}\backslash \{1, \alpha, \beta\}$. For $i+1 \le j\le i+4$, let $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_{j-1}u_j)\}$. Then, $v_{i+5}u_{i+5}$ is a full-edge and $v_{i+3}u_{i+3}$ is an outer-crossing-edge.

If $\alpha \neq 1$ and $\beta = 1$, then set $c(v_iu_i) = 4, \; c(u_iu_{i+1}) = 1, \; c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 3$, $\; c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+4}'') = 1,$ $\; c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4})\in \{2, 4\}\backslash \{\alpha\}$, $\; c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+3})\in \{1, 2, 3, 4\}\backslash \{1, 3, c(v_{i+2}v_{i+3})\},$ $c(v_{i+4}v_{i+5})\in \{1, 2, 3, 4\}\backslash \{1, \alpha, c(v_{i+2}v_{i+3})\}$. For $i+1 \le j\le i+4$, let $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_{j-1}u_j)\}$. Then, $v_{i+5}u_{i+5}$ is a full-edge and $v_{i+3}u_{i+3}$ is an outer-crossing-edge.

If $\alpha = 1$, then $\beta$ may be $2$ or $4$. Consider $\langle \alpha, \beta \rangle = \langle 1, 2 \rangle$. If $G_{i, k}$ is adjacent to a $t$-block with $t\ge 1$, then set $c(u_{i+1}u_{i+2}) = c(v_{i+2}v_{i+3}) = c(v_{i+4}u_{i+4}) = 1$, $c(v_iv_{i+1}) = c(v_{i+3}v_{i+4}) = c(u_{i+2}u_{i+3}) = 2$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(u_{i+3}u_{i+4}) = c(v_{i+4}v_{i+5}) = 3$, $c(u_iu_{i+1}) = c(v_{i+1}v_{i+2}) = c(v_{i+3}u_{i+3}) = c(u_{i+4}u_{i+4}'') = 4$, hence $v_{i+5}u_{i+5}$ is a full-edge and $c(u_{i+4}u_{i+4}'')$ is suitable. If $G_{i, k}$ is adjacent to a $t$-crossing block with $t\ge 2$, then set $c(u_iu_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}v_{i+5}) = 1$, $c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+3}) = c(v_{i+4}u_{i+4}) = c(u_{i+5}u_{i+5}'') = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+6}) = c(v_{i+5}u_{i+5}) = 3$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = c(v_{i+5}v_{i+6}) = 4$, hence $v_{i+6}u_{i+6}$ is a full-edge and $v_{i+5}u_{i+5}$ is a crossing-edge, by Lemma 2.6, the conclusion holds for this case.

Consider $\langle \alpha, \beta \rangle = \langle 1, 4 \rangle$. If $G_{i, k}$ is adjacent to a $t$-block, then set $c(v_{i+1}u_{i+1}) = c(u_{i+2}u_{i+3}) = c(v_{i+3}v_{i+4}) = 1$, $c(v_iv_{i+1}) = c(v_{i+2}u_{i+2}) = c(u_{i+3}u_{i+4}) = c(v_{i+4}v_{i+5}) = 2$, $c(v_iu_i) = c(u_{i+1}u_{i+2}) = c(v_{i+2}v_{i+3}) = c(u_{i+4}u_{i+4}'') = 3$, $c(u_iu_{i+1}) = c(v_{i+1}v_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}u_{i+4}) = 4$, hence $v_{i+5}u_{i+5}$ is a full-edge and $c(u_{i+4}u_{i+4}'')$ is suitable. If $G_{i, k}$ is adjacent to a $t$-crossing block with $t\ge 2$, then set $c(u_iu_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}v_{i+5}) = 1$, $c(v_{i+1}u_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = c(v_{i+5}v_{i+6}) = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+6}) = c(v_{i+5}u_{i+5}) = 3$, $c(v_iu_i) = c(v_{i+1}v_{i+2}) = c(v_{i+4}u_{i+4}) = c(u_{i+5}u_{i+5}'') = 4$, hence $v_{i+6}u_{i+6}$ is a full-edge and $v_{i+5}u_{i+5}$ is a crossing-edge, by Lemma 2.6, the conclusion holds for this case.

Subcase 3.3. $k = 6$.

First assume that $\{\alpha, \beta\} \neq \{1, 3\}$, set $c(v_iu_i) = 4, \; c(u_iu_{i+1}) = 1, \; c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = 3$, $c(v_{i+4}v_{i+5}) = c(u_{i+5}u_{i+5}'') = \beta,$ $\; c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+5})\in \{1, 3\}\backslash \{\alpha, \beta\}$, $c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4})\in \{1, 2, 3, 4\}\backslash \{3, \beta, c(v_{i+3}v_{i+4})\}$, $c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+3})\in \{1, 2, 3, 4\}\backslash \{1, 3, c(v_{i+2}v_{i+3})\}$, $c(v_{i+5}v_{i+6})\in \{1, 2, 3, 4\}\backslash \{\alpha, \beta, c(v_{i+3}v_{i+4})\}$. For $i+1 \le j\le i+5$, let $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_{j-1}u_j)\}$. Then, $v_{i+5}u_{i+5}$ is a full-edge and $v_{i+3}u_{i+3}$ is an outer-crossing-edge.

Consider that $\{\alpha, \beta\} = \{1, 3\}$, since $\overline{c}(u_{i-1})\neq 3$, we have $\alpha = 3$, $\beta = 1$. If $G_{i, k}$ is adjacent to a $t$-block, then set $c(u_{i+1}u_{i+2}) = c(v_{i+2}v_{i+3}) = c(v_{i+4}u_{i+4}) = c(v_{i+5}u_{i+5}) = 1$, $c(v_iv_{i+1}) = c(u_{i+2}u_{i+3}) = c(v_{i+3}v_{i+4}) = c(u_{i+5}u_{i+5}'') = 2$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(u_{i+3}u_{i+4}) = c(v_{i+4}v_{i+5}) = 3$, $c(u_iu_{i+1}) = c(v_{i+1}v_{i+2}) = c(v_{i+3}u_{i+3}) = c(u_{i+4}u_{i+5}) = c(v_{i+5}v_{i+6}) = 4$, hence $v_{i+6}u_{i+6}$ is a full-edge and $c(u_{i+5}u_{i+5}'')$ is suitable. If $G_{i, k}$ is adjacent to a $t$-crossing block with $t\ge 2$, then set $c(u_iu_{i+1}) = c(v_{i+2}v_{i+3}) = c(u_{i+3}u_{i+4}) = c(v_{i+5}u_{i+5}) = c(u_{i+6}u_{i+6}'') = 1$, $c(v_{i+1}v_{i+2}) = c(u_{i+2}u_{i+3}) = c(v_{i+4}v_{i+5}) = c(u_{i+5}u_{i+7}) = c(v_{i+6}u_{i+6}) = 2$, $c(v_iv_{i+1}) = c(u_{i+1}u_{i+2}) = c(v_{i+3}u_{i+3}) = c(v_{i+4}u_{i+4}) = c(v_{i+5}v_{i+6}) = 3$, $c(v_iu_i) = c(v_{i+1}u_{i+1}) = c(v_{i+2}u_{i+2}) = c(v_{i+3}v_{i+4}) = c(u_{i+4}u_{i+5}) = c(v_{i+6}v_{i+7}) = 4$, hence $v_{i+7}u_{i+7}$ is a full-edge and $v_{i+6}u_{i+6}$ is a crossing-edge, by Lemma 2.6, the conclusion holds for this case.

Subcase 3.4. $k\ge 7$.

We first set $c(v_iu_i) = 4, \; c(v_iv_{i+1}) = 3, \; c(u_iu_{i+1}) = 1$, $c(v_{i+k-2}v_{i+k-1}) = \beta$. Since $\langle \alpha, \beta \rangle \notin \{\langle 2, 4 \rangle, \langle 4, 2 \rangle\}$, we may set $c(v_{i+k-3}v_{i+k-2})\in \{2, 4\}\backslash \{\alpha, \beta\}$. For $j = i+k-4, i+k-5, \ldots, i+3$, let $c(v_jv_{j+1})\in \{2, 3, 4\}\backslash \{c(v_{j+1}v_{j+2})), c(v_{j+2}v_{j+3})\}$, then let $c(v_{i+2}v_{i+3}) = 1$, $c(v_{i+1}v_{i+2})\in \{1, 2, 3, 4\}\backslash \{1, 3, c(v_{i+3}v_{i+4})\}$. For $i+1\le j\le i+k-2$, let $c(u_ju_{j+1}) = c(v_{j-1}v_j)$, $c(v_ju_j) = \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_{j-1}u_j)\}$. Finally, let $c(u_{i+k-1}u_{i+k-1}'') = \beta$, $c(v_{i+k-1}v_{i+k}) = \{1, 2, 3, 4\}\backslash \{\alpha, \beta, (v_{i+k-3}v_{i+k-2})\},$ and $c(v_{i+k-1}u_{i+k-1}) = \{1, 2, 3, 4\}\backslash \{c(v_{i+k-2}v_{i+k-1}), c(v_{i+k-1}v_{i+k}), c(u_{i+k-2}u_{i+k-1})\}$. It is easy to see that $c$ is a good coloring, and $\overline{c}(v_j) = c(u_{j-1}u_j), \; c(v_jv_{j+1}) = \overline{c}(u_j)$ for $i+1\le j\le i+k-1$. That is, we have $c(v_{i+k-1}v_{i+k}) = \overline{c}(u_{i+k-1})$. Hence $v_{i+k-1}u_{i+k-1}$ is an outer-crossing-edge since $c(u_{i+k-1}u_{i+k-1}'') = \beta$. Note that, $\overline{c}(v_{i+k-1}) = c(u_{i+k-2}u_{i+k-1}) = c(v_{i+k-3}v_{i+k-2})$, hence $\overline{c}(v_{i+k-1})\notin \{\alpha, \beta\}$. By the fact that $c(v_{i+k-1}v_{i+k}) \notin \{\alpha, \beta\}$ and $c(v_{i+k-1}v_{i+k})\neq \overline{c}(v_{i+k-1})$, we have $v_{i+k}u_{i+k}$ is a full-edge. If $G_{i, k}$ is adjacent to a $t$-block, then $v_{i+k}u_{i+k}$ is a full-edge and $c(u_{i+k-1}u_{i+k-1}'')$ is suitable. If $G_{i, k}$ is adjacent to a $t$-crossing block with $t\ge 2$, by Lemma 2.6, we can extend the coloring $c$ such that $v_{i+k+t-1}u_{i+k+t-1}$ is a full-edge and $c(u_{i+k+t-2}u_{i+k+t-2}'')$ is suitable. □

Remark 2.2. By Lemma 2.6 and the proof of Lemma 2.7, if $G_{i, k}$ is adjacent to a $t$-crossing block $G_{i+k, t, c}$ with $t\ge 2$ and $v_{i+k+t}\neq v_r$, then we can extend the coloring $c$ such that $v_{i+k+t}u_{i+k+t}$ is a full-edge and $c(u_{i+k+t-1}u_{i+k+t-1}'')$ is suitable. Moreover, if $G_{i, k}$ is adjacent to $1$-block, then we can extend the coloring $c$ such that $v_{i+k+1}u_{i+k+1}$ is a full-edge and $c(u_{i+k}u_{i+k}'')$ is suitable.

Lemma 2.8. Suppose $G_{i, k}$ is not a bottom block and $k\ge 2$. If $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is a full-edge, then $c$ can be extended to a good coloring of $G$.

Proof. Assume that $G_{i, k}$ is adjacent to $G_{i+k, t}$. By Lemma 2.7, we can extend $c$ to a good coloring of $G_{i, k}$ such that $v_{i+k}u_{i+k}$ is a full-edge. If $G_{i+k, t}$ is a bottom block, then by Lemma 2.5, $c$ can be extended to a good coloring of $G$ if $t = 1$, or $t\ge 3$, or $t = 2$ and $c(u_{i+k-1}u_{i+k-1}'')$ is suitable. For $t = 2$ and $c(u_{i+k-1}u_{i+k-1}'')$ is not suitable, by Lemma 2.7, $c$ can also be extended to a good coloring of $G$.

Therefore, we assume that $G_{i+k, t}$ is not a bottom block. If $t\ge 2$, then the argument is similar as above. So assume that $t = 1$, that is, $v_{i+k}u_{i+k}$ is in a crossing block. Suppose $v_{i+k}u_{i+k}$ is in a $l$-crossing block and $l$ is maximal, that is, $v_{i+k+l-1}u_{i+k+l-1} = v_{r-1}u_{r-1}$ or $v_{i+k+l}u_{i+k+l}$ is in a $d$-block with $d\ge 2$. For $l = 1$, since $G_{i+k, t}$ is not a bottom block, $v_{i+k+1}u_{i+k+1}$ is in a $d$-block with $d\ge 2$. By Remark 2.2, we can extend the coloring $c$ such that $v_{i+k+1}u_{i+k+1}$ is a full-edge and $c(u_{i+k}u_{i+k}'')$ is suitable. If this $d$-block is a bottom block, then we can extend $c$ to a good coloring of $G$ by Lemma 2.5. If this $d$-block is not a bottom block, then we make the same argument as the case $G_{i, k}$. If $l\ge 2$, then by Lemma 2.7, we can extend $c$ to a good coloring of $G_{i+k, l, c}$ such that $v_{i+k+l-1}u_{i+k+l-1}$ is a full-edge and $c(u_{i+k+l-2}u_{i+k+l-2}'')$ is suitable. Hence, if $v_{i+k+l-1}u_{i+k+l-1} = v_{r-1}u_{r-1}$, then by Lemma 2.5, $c$ can be extended to a good coloring of $G$. For the case $v_{i+k+l}u_{i+k+l}$ is in a $d$-block with $d\ge 2$, by Remark 2.2, we can extend $c$ such that $v_{i+k+t}u_{i+k+t}$ is a full-edge and $c(u_{i+k+t-1}u_{i+k+t-1}'')$ is suitable. Hence if this $d$-block is a bottom block, then we can extend $c$ to a good coloring of $G$ by Lemma 2.5. If this $d$-block is not a bottom block, then we make the same argument as the case $G_{i, k}$. □

Corollary 2.1. Let $G_{i, k}$ be a $k$-block with $k\ge 2$. If $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is a full-edge and $c(u_{i-1}u_{i-1}'')$ is suitable, then $c$ can be extended to a good coloring of $G$.

Corollary 2.2. Let $G_{i, k}$ be a $k$-block. If $H_{i, k}$ has a good coloring $c$ such that $v_iu_i$ is a full-edge and $v_{i-1}u_{i-1}$ is a crossing-edge or an outer-crossing-edge, then $c$ can be extended to a good coloring of $G$.

Proof. Note that $c(u_{i-1}u_{i-1}'')$ is suitable since $v_{i-1}u_{i-1}$ is a crossing-edge or an outer-crossing-edge. So if $G_{i, k}$ is a bottom block, then $c$ can be extended to a good coloring of $G$ by Lemma 2.5. If $G_{i, k}$ is not a bottom block and $k\ge 2$, by Lemma 2.8, we can extend $c$ to a good coloring of $G$. Hence we only need to consider that $G_{i, k}$ is not a bottom block and $k = 1$. For this case, $v_iu_i$ is in a crossing block, with the similar argument as Lemma 2.8, we can extend $c$ + to a good coloring of $G$. □

Theorem 2.2. For every cubic Halin graph $G$ in $\mathcal{G}_r$ which is not a necklace $N_r$, $\chi'_{avd}(G) = 4$.

Proof. Since $G$ is not a necklace $N_r$, there are at least two blocks in $G$. Suppose the block containing $v_2u_2$ is a $k$-block.

Case 1. $k = 1$.

In this case, $u_2$ and $u_3$ are on the different sides of $P$. We set $c(v_1u_1) = c(v_2u_2) = 1, \; c(v_1u_0) = c(u_2u_2'') = 2, \; c(u_0u_1) = c(v_2v_3) = 3, \; c(u_1u_2) = c(v_1v_2) = c(u_0u_3) = 4$. Then $v_3u_3$ becomes a full-edge and $v_2u_2$ becomes a crossing-edge. By Corollary 2.2, $c$ can be extended to a good coloring of $G$.

Case 2. $k = 2$.

Suppose the block $G_{2, k}$ is adjacent to $G_{4, t}$. If $t\ge 2$, then let $c(v_1u_1) = c(v_2u_2) = c(v_3u_3) = \; 1, \; c(v_1u_0) = c(u_2u_3) = c(v_3v_4) = 2$, $c(u_0u_1) = c(v_1v_2) = c(u_3u_3'') = 3, \; c(u_1u_2) = c(v_2v_3) = c(u_0u_4) = 4$. Then $v_4u_4$ becomes a full-edge and $c(u_3u_3'')$ is suitable. Hence, by Corollary 2.1, we can extend $c$ to a good coloring of $G$.

For $t = 1$, that is $u_5$ and $u_4$ are on the different sides of $P$. If $v_5u_5$ is in a $l$-block with $l\ge 2$, then let $c(u_1v_1) = c(v_2v_3) = c(u_3u_5) = c(v_4u_4) = 1$, $c(v_1u_0) = c(u_1u_2) = c(v_3v_4) = 2$, $c(u_0u_1) = c(v_2u_2) = c(v_3u_3) = c(u_4u_4'') = 3$, $c(v_1v_2) = c(u_0u_4) = c(u_2u_3) = c(v_4v_5) = 4$. Then $v_5u_5$ becomes a full-edge and $c(v_4u_4)$ is suitable. Hence, by Corollary 2.1, we can extend $c$ to a good coloring of $G$. Therefore, $v_5u_5$ is in a $1$-block, which means $u_6$ and $u_5$ are on the different sides of $P$.

Consider the edge $v_6u_6$ is in a $d$-block, let $c(u_1v_1) = c(u_2u_3) = c(v_3v_4) = c(u_4u_6) = c(v_5u_5) = 1$, $c(v_1u_0) = c(v_2u_2) = c(v_3u_3) = c(v_4v_5) = 2$, $c(u_0u_1) = c(v_1v_2) = c(u_3u_5) = c(v_4u_4) = 3$, $c(u_1u_2) = c(u_0u_4) = c(v_2v_3) = c(v_5v_6) = c(u_5u_5'') = 4$. Then $v_6u_6$ becomes a full-edge while $c(u_4u_5)$ is not suitable. If $G_{6, d}$ is not a bottom block and $d\ge 2$, then by Lemma 2.8, we can extend $c$ to a good coloring of $G$. If $G_{6, d}$ is a bottom block with $d = 1$ or $d\ge 3$, then by Lemma 2.5, we can extend $c$ to a good coloring of $G$. If $G_{6, d}$ is a bottom block with $d = 2$, then $G$ is the graph $H_0$ depited in Figure. For this case, we give a good coloring of $H_0$ as follows: let $c(v_1u_1) = c(v_2u_2) = c(u_3u_5) = c(v_4v_5) = c(u_4u_6) = c(v_7v_8) = c(u_8u_9) = 1$, $c(v_1u_0) = c(u_2u_3) = c(v_3v_4) = c(v_5v_6) = c(u_6u_7) = c(v_8u_9) = 2$, $c(u_1u_0) = c(v_1v_2) = c(v_3u_3) = c(v_4u_4) = c(u_5u_9) = c(v_6v_7) = c(u_7u_8) = 3$, $c(u_1u_2) = c(u_0u_4) = c(v_2v_3) = c(v_5u_5) = c(v_6u_6) = c(v_7u_7) = c(v_8u_8) = 4$.

Now we consider that $G_{6, d}$ is not a bottom block and $d = 1$. Let $c(u_1v_1) = c(u_2u_3) = c(v_3v_4) = c(u_4u_6) = c(u_5u_7) = c(v_5v_6) = 1$, $c(v_1u_0) = c(v_2u_2) = c(v_3u_3) = c(v_4v_5) = c(v_6u_6) = 2$, $c(u_0u_1) = c(v_1v_2) = c(u_3u_5) = c(v_4u_4) = c(v_6v_7) = 3$, $c(u_1u_2) = c(u_0u_4) = c(v_2v_3) = c(v_5u_5) = c(u_6u_6'') = 4$. Then $v_7u_7$ becomes a full-edge and $v_6u_6$ becomes a crossing-edge. By Corollary 2.2, we can extend $c$ to a good coloring of $G$.

Case 3. $k\ge 3$.

We first give a good coloring of $G_1$ as follows: $c(u_1v_1) = 1, \; c(v_1u_0) = 2, \; c(u_0u_1) = 3$, $c(u_1u_2) = \; 2, \; c(v_1v_2) = c(u_0u_{2+k}) = 4$. Then $\langle c(u_0u_{2+k}), \overline{c}(u_0) \rangle = \langle 4, 1 \rangle$. Now we color the block $G_{2, k}$.

For $k = 3$, set $c(v_2u_2) = c(v_3v_4) = c(u_4u_4'') = 1$, $c(v_3u_3) = c(v_4v_5) = 2$, $c(v_2v_3) = c(u_3u_4) = 3$, and $c(u_2u_3) = c(v_4u_4) = 4$, then $v_5u_5$ is a full-edge and $v_4u_4$ is an outer-crossing edge.

For $k = 4$, set $c(v_2u_2) = c(v_3u_3) = c(v_4v_5) = c(u_5u_5'') = 1$, $c(v_3v_4) = c(u_4u_5) = 2$, $c(v_2v_3) = c(u_3u_4) = c(v_5v_6) = 3$, and $c(u_2u_3) = c(v_4u_4) = c(v_5u_5) = 4$, then $v_6u_6$ is a full-edge and $v_5u_5$ is an outer-crossing edge.

For $k = 5$, set $c(v_2v_3) = c(u_3u_4) = c(v_5v_6) = c(u_6u_6'') = 1$, $c(v_3u_3) = c(v_4v_5) = c(u_5u_6) = 2$, $c(v_2u_2) = c(v_3v_4) = c(u_4u_5) = c(v_6v_7) = 3$, and $c(u_2u_3) = c(v_4u_4) = c(v_5u_5) = c(v_6u_6) = 4$, then $v_7u_7$ is a full-edge and $v_6u_6$ is an outer-crossing edge.

For $k\ge 6$, first set $c(v_2v_3) = 1$, $c(v_3v_4) = 3$. For $4\le j\le k-2$, let $c(v_jv_{j+1})\in \{1, 2, 3\}\backslash \{c(v_{j-2}v_{j-1}), c(v_{j-1}v_j)\}$. Then let $c(v_{k-2}v_{k-1}) = 4$, $c(v_{k-1}v_k)\in \{2, 3\}\backslash \{c(v_{k-3}v_{k-2})\}$, $c(v_kv_{k+1}) = \; 1$, $c(v_{k+1}v_{k+2})\in \{2, 3\}\backslash \{c(v_{k-1}v_k)\}$. For $2\le j\le k$, let $c(u_ju_{j+1}) = c(v_{j-1}v_j)$ and $c(v_ju_j)\in \{1, 2, 3, 4\}\backslash \{c(v_{j-1}v_j), c(v_jv_{j+1}), c(u_{j-1}u_j)\}$. Finally, let $c(u_{k+1}u_{k+1}'') = 1$ and $c(v_{k+1}u_{k+1}) = 4$. Then $c$ is a good coloring of $G_{2, k}$, $v_{k+2}u_{k+2}$ is a full-edge and $v_{k+1}u_{k+1}$ is an outer-crossing edge.

By Corollary 2.2, we can extend $c$ to a good coloring of $G$.

In summary, we have $\chi'_{avd}(G)\le 4$. On the other hand, since $G$ is cubic, $\chi'_{avd}(G)\ge 4$. Therefore, $\chi'_{avd}(G) = 4$. □

Combining Theorem 2.1 and Theorem 2.2, we complete the proof of Theorem 1.2.

3.   Conclusions

In this paper, we have determined the exact values of the adjacent vertex distinguishing (AVD) chromatic indices of cubic Halin graphs whose characteristic trees are caterpillars. We showed that only two graphs have AVD chromatic index 5. For the cubic Halin graphs whose characteristic trees are not caterpillars, we believe that there are few graphs obtaining AVD chromatic index 5. It is interesting to figure out which cubic Halin graphs with characteristic trees not caterpillars have AVD chromatic index 5.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors are grateful to reviewers for their valuable comments and suggestions. This work is supported by the Natural Science Foundation of Fujian Province (No.2020J05058) and the Fundamental Research Funds for the Central Universities of Huaqiao University (ZQN-903).

Conflict of interest

The authors declare no conflict of interest.