A Characterization for the Neighbor-Distinguishing Index of Planar Graphs

Abstract

Symmetry, such as structural symmetry, color symmetry and so on, plays an important role in graph coloring. In this paper, we use structural symmetry and color symmetry to study the characterization for the neighbor-distinguishing index of planar graphs. Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any two adjacent vertices admit different sets consisting of the colors of their incident edges. The neighbor-distinguishing index ${\chi }_a^{\prime }\left(G\right)$ of G is the smallest number of colors in such an edge coloring of G. It was conjectured that if G is a connected graph with at least three vertices and $G\ne C_5$, then ${\chi }_a^{\prime }\left(G\right)\le \Delta +2$. In this paper, we show that if G is a planar graph with maximum degree $\Delta \ge 13$, then $\Delta \le {\chi }_a^{\prime }\left(G\right)\le \Delta +1$, and, further, ${\chi }_a^{\prime }\left(G\right)=\Delta +1$ if and only if G contains two adjacent vertices of maximum degree.

1. Introduction

The symmetry of graphs is always an important research topic in graph theory. In practical applications, the symmetry of graphs is closely related to coding, cryptography, computer network design and computer network security. In recent years, with the rapid development of large-scale computer systems and interconnection networks, the study of the symmetry of graphs has become more and more important.

In this paper, we use symmetry to study the characterization for the neighbor- distinguishing index of planar graphs. We consider that all graphs are finite and simple. A plane graph is a particular drawing of a planar graph without any two of its edge crossing on the Euclidean plane. Suppose that G is a plane graph with vertex set $V\left(G\right)$, edge set $E\left(G\right)$, face set $F\left(G\right)$, minimum degree $\delta \left(G\right)$ and maximum degree $\Delta \left(G\right)$ (for short, $\Delta$). Let $\left|V\right(G\left)\right|$ and $\left|E\right(G\left)\right|$ denote the order and size of G, respectively. For an element $x\in V\left(G\right)\cup F\left(G\right)$, the degree of x is denoted by $d_G\left(x\right)$ in G. A vertex of degree k (at least k, at most k) in G is a k-vertex ($k^{+}$-vertex, $k^{-}$-vertex). Likewise, we may define k-face, $k^{+}$-face and $k^{-}$-face. For positive integers $p,q,r,s$ with $p<q$, $[p,q]$ is used to denote the set of positive integers $\{p,p+1,\dots ,q\}$. If $r\ne s$ and $r,s\notin [p,q]$, then $\{p-q,r,s\}$ denote the set of positive integers $[p,q]\cup \{r,s\}$.

For a graph G, a proper edge k-coloring of G is a mapping $\varphi$ from $E\left(G\right)$ to $[1,k]$ such that any two adjacent edges are colored with different colors. The chromatic index ${\chi }^{\prime }\left(G\right)$ of G is the smallest positive integer k for which G has a proper edge k-coloring. For a proper edge k-coloring $\varphi$ of G and a vertex $v\in V\left(G\right)$, $C_{\varphi }\left(v\right)=\left\{\varphi \left(uv\right)\right|uv\in E\left(G\right)\}$ is used to denote the set of colors of the edges incident with v. The proper edge k-coloring $\varphi$ of G is neighbor-distinguishing (or $\varphi$ is an NDE-k-coloring of G) if $C_{\varphi }\left(u\right)\ne C_{\varphi }\left(v\right)$ for each edge $uv\in E\left(G\right)$. The neighbor-distinguishing index${\chi }_a^{\prime }\left(G\right)$ of G is the smallest positive integer k for which G has an NDE-k-coloring.

A graph G without isolated edges is normal. Obviously, G is normal if and only if G has an NDE-coloring. Therefore, in the following discussion, we always assume that G is normal. We see easily that ${\chi }_a^{\prime }\left(G\right)\ge {\chi }^{\prime }\left(G\right)\ge \Delta$ for any normal graph G. If G has connected components $G_1$,$G_2,\dots ,G_k$, then ${\chi }_a^{\prime }\left(G\right)=max\left\{{\chi }_a^{\prime }\left(G_i\right)\right|i\in [1,k]\}$. If G contains two adjacent $\Delta$-vertices, then ${\chi }_a^{\prime }\left(G\right)\ge \Delta +1$. Zhang et al. [1] first introduced the NDE-coloring of graphs. After they determined the neighbor-distinguishing indices of some special graphs, they put forward the following conjecture:

Conjecture 1.

If G is a connected graph with $\left|V\right(G\left)\right|\ge 3$ and $G\ne C_5$, then ${\chi }_a^{\prime }\left(G\right)\le \Delta +2$.

Conjecture 1 was confirmed by Balister et al. [2] for bipartite graphs and graphs with $\Delta =3$. Akbari et al. [3] established that ${\chi }_a^{\prime }\left(G\right)\le 3\Delta$ for any normal graph G. This result is refined gradually to that of ${\chi }_a^{\prime }\left(G\right)\le 2.5\Delta +5$ in [4], to that of ${\chi }_a^{\prime }\left(G\right)\le 2.5\Delta$ in [5] and to that of ${\chi }_a^{\prime }\left(G\right)\le 2\Delta +2$ in [6]. By means of the probabilistic method, Hatami [7] confirmed that every normal graph G for a large enough $\Delta$ has ${\chi }_a^{\prime }\left(G\right)\le \Delta +300$. Recently, Joret and Lochet [8] reduced this upper bound to $\Delta +19$.

If we focus on the class of planar graphs, then Conjecture 1 is true when $\Delta \ge 11$. This was proved in [9] for $\Delta \ge 12$ and in [10] for $\Delta =11$. Furthermore, in 2015, Wang and Huang [11] gave the following stronger results:

(a) 

If $\Delta \ge 15$, then $\Delta \le {\chi }_a^{\prime }\left(G\right)\le \Delta +1$.

(b) 

If $\Delta \ge 16$, then ${\chi }_a^{\prime }\left(G\right)=\Delta +1$ if and only if G contains two adjacent $\Delta$-vertices.

The condition that $\Delta \ge 15$ in the conclusion $\left(a\right)$ has been improved to that of $\Delta \ge 12$ in [12]. Recently, the conclusion $\left(b\right)$ has been extended to the case of $\Delta \ge 14$ in [13]. In this paper, we continue to improve $\left(b\right)$ to the case of $\Delta \ge 13$. To be more precise, we will show the following:

Theorem 1. 

Suppose that G is a planar graph with $\Delta \ge 13$. Then ${\chi }_a^{\prime }\left(G\right)=\Delta +1$ if and only if G contains two adjacent Δ-vertices.

2. Preliminaries

Suppose that H is a subgraph of a plane graph G. For a vertex $v\in V\left(H\right)$, let $N_H\left(v\right)$ ($N_k^H\left(v\right)$) denote the set of vertices (k-vertices) adjacent to v in H. Set $d_k^H\left(v\right)=\left|N_k^H\left(v\right)\right|$ and $N_{i_1,i_2,\dots ,i_k}^H\left(v\right)=N_{i_1}^H\left(v\right)\cup N_{i_2}^H\left(v\right)\cup \dots \cup N_{i_k}^H\left(v\right)$. We may define $N_{k^{+}}^H\left(v\right)$, $N_{k^{-}}^H\left(v\right)$, $d_{k^{+}}^H\left(v\right)$ and $d_{k^{-}}^H\left(v\right)$, similarly. For a face $f\in F\left(H\right)$, we use $d_k^H\left(f\right)$ ($d_{k^{+}}^H\left(f\right)$, $d_{k^{-}}^H\left(f\right)$) to denote the number of k-vertices ($k^{+}$-vertices, $k^{-}$-vertices) incident with f in H. To avoid contextual confusion, we omit the letter G in $d_G\left(v\right),d_k^G\left(v\right),d_{k^{+}}^G\left(v\right),d_{k^{-}}^G\left(v\right),d_k^G\left(f\right)$, $d_{k^{+}}^G\left(f\right)$ and $d_{k^{-}}^G\left(f\right)$.

In the plane graph H, an n-cycle $v_1{v}_2\cdots v_n{v}_1$ is a $(d_1,d_2,\dots ,d_n)$-cycle with $d_H\left(v_i\right)=d_i$ for each $i\in [1,n]$. A 3-cycle with one 2-vertex is special. A 3-cycle with two 3-vertices is bad. A 4-cycle with two 2-vertices is special. For $l\in [3,4]$, an l-face is special or bad if its boundary forms a special or bad l-cycle. A vertex v with $d_H\left(v\right)\in [1,5]$ is small. A 3-vertex v is a $T_1^2$-3-vertex if $d_3^H\left(v\right)=1$ and two of the faces incident with v are 3-faces.

Given a graph G, for $i\in [1,\Delta (G\left)\right]$, we use $n_i\left(G\right)$ to denote the number of i-vertices in $V\left(G\right)$. We say that G is smaller than a graph H if $\left(\right|E\left(G\right)|,n_t\left(G\right),n_{t-1}\left(G\right),\dots ,n_1\left(G\right))$ precedes $\left(\right|E\left(H\right)|,n_t\left(H\right),n_{t-1}\left(H\right),\dots ,n_1\left(H\right))$ with respect to the standard lexicographic order, where $t=max\{\Delta (G),\Delta (H\left)\right\}$. A graph is minimal with respect to a given property P when there is no smaller graph with the property P.

Suppose that $\varphi$ is an NDE-k-coloring of the graph G, and u is adjacent to v in G. It is evident that $C_{\varphi }\left(u\right)\ne C_{\varphi }\left(v\right)$ when $d_G\left(u\right)\ne d_G\left(v\right)$. If $C_{\varphi }\left(u\right)=C_{\varphi }\left(v\right)$, then u and v are conflicting under ϕ. The edge $uv$ is legally colored if it is colored with a color that is different from the colors of its adjacent edges in $E\left(G\right)$, and there are not any pairs of new conflicting vertices.

3. Proofs

To prove Theorem 1, we only need to prove the following:

Theorem 2. 

Suppose that G is a planar graph with $\Delta =13$. Then ${\chi }_a^{\prime }\left(G\right)=14$ if and only if G contains two adjacent 13-vertices.

Proof. 

If G contains two adjacent 13-vertices, then ${\chi }_a^{\prime }\left(G\right)\ge 13+1=14$. It can be obtained from [12] that ${\chi }_a^{\prime }\left(G\right)\le 14$ if $\Delta =13$. Then, the necessity is clearly illustrated by the previous discussion. To demonstrate sufficiency, it is adequate to show that ${\chi }_a^{\prime }\left(G\right)\le 13$ for a planar graph G with $\Delta =13$ and without adjacent 13-vertices. Let us say that it is not true. Suppose that G is a minimal counterexample of Theorem 2, that is to say, G has no NDE-13-coloring, while any other planar graph H smaller than G has an NDE-13-coloring. It is obvious that G is connected. As G does not contain two adjacent 13-vertices, it is easy to deduce that a 1-vertex is not adjacent to a 13-vertex. Let $C=[1,13]$ denote a set of 13 colors, and we use C as the color set in the following discussion. □

3.1. Structural Properties in G

In this subsection, we discuss the structural properties of the minimal counterexample G by a series of auxiliary claims. A cut vertex v is nontrivial if there are at least two components of $G-v$ with an order of at least 2. If v is a k-vertex, then we use $v_1,v_2,\dots ,v_k$ to denote the vertices adjacent to v.

Claim 1 

(Wang and Huang, [11]). There is no nontrivial cut vertex in G.

Claim 2. 

A 1-vertex is not adjacent to a $7^{-}$-vertex in G.

Proof. 

Assume to the contrary that G contains an edge $uv$ with $d\left(u\right)=1$ and $d\left(v\right)\le 7$. Then, $G-u$ admits an NDE-13-coloring $\varphi$ by the minimality of G. As $uv$ has at most 12 forbidden colors, we color $uv$ with a color in $C\backslash C_{\varphi }\left(v\right)$ such that v does not conflict with the vertices adjacent to v. This gives an NDE-13-coloring of G, a contradiction. □

Claim 3 

(Cheng et al. [10]). Let $v\in$$V\left(G\right)$ with $d\left(v\right)=k$.

(1) 

If $k=2$, then $d_2\left(v\right)=0$.

(2) 

If $k\in [3,5]$, then $d_k\left(v\right)\le 1$.

(3) 

If $k\le 6$, then $d_i\left(v\right)=0$ for $i\in [1,k-1]$.

(4) 

If $k\in [7,8]$ and $d_{4^{-}}\left(v\right)\ge 1$, then $d_{5^{-}}\left(v\right)\le k-6$.

Claim 4 

(Wang et al. [13]). Let $v\in V\left(G\right)$.

(1) 

If $d_1\left(v\right)\ge k\in [1,4]$, then $d_s\left(v\right)=0$ for $s\in [2,k+1]$.

(2) 

If $d\left(v\right)\le 12$, then $d_2\left(v\right)\le 1$.

(3) 

v is not in any special 4-cycle.

(4) 

If v is in a special 3-cycle, then $d_2\left(v\right)=1$.

Claim 5. 

Let $v\in$$V\left(G\right)$ with $d\left(v\right)=k\ge 8$.

(1) 

v is in at most one bad 3-cycle. Further, if v is in a bad 3-cycle, then $k\ge 11$ and $d_{2^{-}}\left(v\right)=0$.

(2) 

If v is in $G_1$ of Figure 1, then $d_{3^{-}}\left(v\right)=2$.

(3) 

G contains none of the configurations $G_i$ for $i\in [2,5]$, as shown in Figure 1.

In Figure 1, black (white) dots are used to mark the vertices whose degrees are exactly (at least) the one shown in the configurations.

Proof. 

$\left(1\right)$ In the first place, we prove that v is in at most one bad 3-cycle. Assume to the contrary that v is in two bad 3-cycles. Let us say that $d\left(v_i\right)=3$ for $i\in [1,4]$ and $v_1{v}_2,v_3{v}_4\in E\left(G\right)$. We use $u_i$ to denote the third vertex adjacent to $v_i$ for $i\in [1,4]$. Then, $G-v_1{v}_2$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,k]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(v_2\right)$, then $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G. Assume that $C_{\varphi }\left(v_1\right)$$=C_{\varphi }\left(v_2\right)=\{1,2\}$, that is, $\varphi \left(v_1{u}_1\right)=2$ and $\varphi \left(v_2{u}_2\right)=1$. Notice that $\varphi \left(v_3{u}_3\right)\ne 4$ or $\varphi \left(v_4{u}_4\right)\ne 3$, say $\varphi \left(v_3{u}_3\right)\ne 4$. We remove the color of $v_3{v}_4$. We recolor $v{v}_3$ with a color in $\{1,2\}\backslash \left(\varphi \left(v_3{u}_3\right)\right)$, say 1, and $v{v}_1$ with 3. Then, $v_1{v}_2$, $v_3{v}_4$ are colored properly to obtain an NDE-13-coloring of G, which is a contradiction.

In the second place, suppose that v is in a bad 3-cycle. Let $v_1{v}_2\in E\left(G\right)$ with $d\left(v_1\right)=d\left(v_2\right)=3$. Then, $G-v_1{v}_2$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,k]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(v_2\right)$, then $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(v_2\right)=\{1,2\}$.

• Prove that $k\ge 11$. Assume to the contrary that $k\le 10$. Firstly, $v{v}_1$ or $v{v}_2$ is recolored with any color in $[11,13]$. Secondly, we recolor $v{v}_1$ with 11 and $v{v}_2$ with 12 or 13. Thirdly, we recolor $v{v}_1$ with 12 and $v{v}_2$ with 13. We can find at least nine different ways to recolor $v{v}_1$ or $v{v}_2.$ Since v has at most eight conflict vertices, we may extend $\varphi$ to G, which is a contradiction.
• Prove that $d_{2^{-}}\left(v\right)=0$. Assume to the contrary that $d\left(v_3\right)\le 2.$ By Claim 3(1), $v_3$ does not have any conflicting vertices. We recolor $v{v}_3$ with a color in $\{1,2\}\backslash C_{\varphi }\left(v_3\right)$, say 1, and $v{v}_1$ with 3. Then, $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G, which is a contradiction.

$\left(2\right)$ Assume to the contrary that $d_{3^{-}}\left(v\right)\ge 3$. By Claim 5(1), we can conclude that $d_{2^{-}}\left(v\right)=0$. Let $d\left(v_4\right)=3$. We use the same vertex labels as shown in $G_1$ of Figure 1. Then, $G-v_1{v}_2$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,k]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(v_2\right)$, then $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(v_2\right)=\{1,2\}$, that is, $\varphi \left(v_1{v}_3\right)=2$ and $\varphi \left(v_2{v}_3\right)=1$.

If $d_3\left(v_4\right)=0$, then $v{v}_4$ is recolored with a color $\alpha \in [1,3]\backslash C_{\varphi }\left(v_4\right)$ such that $v_4$ does not conflict with the vertices adjacent to $v_4$. If $d_3\left(v_4\right)=1$, say, $x_4\in N\left(v_4\right)$ with $d\left(x_4\right)=d\left(v_4\right)=3$, then $v_4{x}_4$ is recolored with a color in $[4,13]\backslash (C_{\varphi }\left(v_4\right)\cup C_{\varphi }\left(x_4\right))$. Let $\beta \in C_{\varphi }\left(x_4\right)\backslash C_{\varphi }\left(v_4\right)$. Then, $v{v}_4$ is recolored with a color $\alpha \in [1,3]\backslash ((C_{\varphi }\left(v_4\right)\backslash \{\varphi \left(v_4{x}_4\right),\varphi \left(v{v}_4\right)\})\cup \left\{\beta \right\})$. Hence, there exists a color $\alpha \in [1,3]$ such that, if $v{v}_4$ is recolored with $\alpha$, then $v_4$ does not conflict with the vertices adjacent to $v_4$. If $\alpha =i\in [1,2]$, then $v{v}_i$ is recolored with 4. If $\alpha =3$, then we recolor $v{v}_1$ with 4, $v{v}_3$ with 1 and $v_2{v}_3$ with 3. Then, $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G, which is a contradiction.

$\left(3\right)$ The proof that G does not contain $G_2$ and $G_3$ has been provided in [13]. Now, we will prove it in two cases and use the same vertex labels as shown in Figure 1.

Case 1. Suppose that G contains $G_4$. By Claims 3 and 5(1), we can conclude that $d\left(v_1\right)$, $d\left(v_4\right)\ge 7$. We split $v_2$ into two 1-vertices, $x_1$ and $x_2$, such that v is adjacent to $x_1$, and $v_1$ is adjacent to $x_2$. Then, the resultant graph H admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_1\right)=1$, $\varphi \left(v{x}_1\right)=2$ and $\varphi \left(v{v}_i\right)=i$ for $i\in [3,k]$. We stick $x_1$ and $x_2$ to restore the graph G. If $\varphi \left(v_1{x}_2\right)\ne 2$, we are done. Otherwise, $\varphi \left(v_1{x}_2\right)=2$. Then, we discuss two subcases as follows.

Case 1.1.$d_3\left(v_3\right)=0$. Let $\alpha \in \{1,2\}\backslash \{\varphi \left(v_3{u}_3\right),\varphi \left(v_3{v}_4\right)\}$. If $\alpha =1$, then we recolor $\{v{v}_3,v_1{x}_2\}$ with 1, $v{v}_1$ with 2 and $v{x}_1$ with 3. If $\alpha =2$, then we recolor $v{x}_1$ with 3. If $\varphi \left(v_3{u}_3\right)=1$ and $\varphi \left(v_3{v}_4\right)=2$, then we recolor $\{v_3{v}_4,v{x}_1\}$ with 4 and $v{v}_4$ with 2. If $\varphi \left(v_3{v}_4\right)=1$ and $\varphi \left(v_3{u}_3\right)=2$, then we recolor $\{v_3{v}_4,v{x}_1\}$ with 4, $\{v{v}_4,v_1{x}_2\}$ with 1 and $v{v}_1$ with 2.

Case 1.2.$d_3\left(v_3\right)=1$, that is, $d\left(u_3\right)=d\left(v_3\right)=3$. By Claim 3, we can conclude that each vertex in $N\left(v_3\right)\cup N\left(u_3\right)\backslash \{v_3,u_3\}$ is a $7^{+}$-vertex in G. The color of $v_3{u}_3$ is removed. Let $\beta \in C_{\varphi }\left(u_3\right)\backslash C_{\varphi }\left(v_3\right)$ and $\alpha \in$$\{1,2\}\backslash \{\varphi \left(v_3{v}_4\right),\beta \}$. If $\alpha =1$, then we recolor $\{v{v}_3,v_1{x}_2\}$ with 1, $v{v}_1$ with 2 and $v{x}_1$ with 3. If $\alpha =2$, then we recolor $v{x}_1$ with 3. If $\beta =1$ and $\varphi \left(v_3{v}_4\right)=2$, then we recolor $\{v_3{v}_4,v{x}_1\}$ with 4 and $v{v}_4$ with 2. If $\varphi \left(v_3{v}_4\right)=1$ and $\beta =2$, then we recolor $\{v_3{v}_4,v{x}_1\}$ with 4, $\{v{v}_4,v_1{x}_2\}$ with 1 and $v{v}_1$ with 2. Finally, we color $v_3{u}_3$ properly to obtain an NDE-13-coloring of G, which is a contradiction.

Case 2. Suppose that G contains $G_5$. As can be seen from Figure 1, $G_5$ is a symmetric configuration. We split $v_2$ into one 1-vertex $x_1$ and one 2-vertex $x_2$ such that $x_1$ is adjacent to v and $x_2$ is adjacent to $v_1$ and $v_3$; and $v_4$ into one 1-vertex $y_1$ and one 2-vertex $y_2$ such that $y_1$ is adjacent to v and $y_2$ is adjacent to $v_3$ and $v_5$. Then, the resultant graph H admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in \{1,3,5\}$, $\varphi \left(v{x}_1\right)=2$, $\varphi \left(v{y}_1\right)=4$, $\varphi \left(v_1{x}_2\right)=a$, $\varphi \left(v_3{x}_2\right)=b$, $\varphi \left(v_3{y}_2\right)=c$ and $\varphi \left(v_5{y}_2\right)=d$. If $\{x_1,x_2\}$ and $\{y_1,y_2\}$ can be stuck together properly, then we obtain an NDE-13-coloring $\varphi$ of G, which is a contradiction. Otherwise, we discuss two subcases as follows.

Case 2.1. If there is exactly one pair, say $\{x_1,x_2\}$, that cannot be stuck together properly, then $2\in \{a,b\}$ and $4\notin \{c,d\}$. We consider $a=2$ (the case $b=2$ can be proved with similar arguments). Sticking $\{x_1,x_2\}$ and $\{y_1,y_2\}$, we restore the graph G. Based on symmetry, we analyze the following possibilities.

• $2\notin \{c,d\}$. If $b\ne 4$, then we exchange the colors of $v{x}_1$ and $v{y}_1$. Otherwise, $b=4$. We exchange the colors of $v{x}_1$ and $v{y}_1$, and the colors of $v_3{x}_2$ and $v_3{y}_2$.
• $c=2$ and $d\ne 3$. We recolor $\{v_3{y}_2,v{x}_1\}$ with 3 and $v{v}_3$ with 2.
• $c=2$, $d=3$ and $b\ne 5$. We exchange the colors of $v{v}_5$ and $v_5{y}_2$ and the colors of $v{v}_3$ and $v_3{y}_2$, and recolor $v{x}_1$ with 5.
• $c=2$, $d=3$ and $b=5$. We exchange the colors of $v{v}_1$ and $v_1{x}_2$ and recolor $v{x}_1$ with 4, $v{y}_1$ with 1.
• $d=2$ and $5\notin \{b,c\}$. We exchange the colors of $v{v}_5$ and $v_5{y}_2$ and recolor $v{x}_1$ with 5.
• $d=2$ and $b=5$. We exchange the colors of $v{v}_5$ and $v_5{y}_2$, and the colors of $v{v}_3$ and $v_3{x}_2$, and recolor $v{x}_1$ with 4 and $v{y}_1$ with 3.
• $d=2$ and $c=5$. We exchange the colors of $v{v}_5$ and $v_5{y}_2$, and the colors of $v{v}_3$ and $v_3{y}_2$, and recolor $v{x}_1$ with 3.

Case 2.2. If no pair can be stuck together properly, then we can assert that $a=c=2$ and $b=d=4$. We exchange the colors of $v{v}_1$ and $v_1{x}_2$, and the colors of $v{v}_5$ and $v_5{y}_2$, and recolor $v{x}_1$ with 5 and $v{y}_1$ with 1. Thus, $\{x_1,x_2\}$ and $\{y_1,y_2\}$ could be stuck together properly to obtain an NDE-13-coloring of G, which is a contradiction. □

Claim 6. 

Let $v\in V\left(G\right)$ with $d\left(v\right)=9$. If $d_{k^{-}}\left(v\right)\ge 1$, then $d_{6^{+}}\left(v\right)\ge (5-k)d_{4^{-}}\left(v\right)+1$ for $k\in [1,4]$.

Proof. 

Assume to the contrary that $d_{6^{+}}\left(v\right)\le (5-k)d_{4^{-}}\left(v\right)$. Let $d\left(v_1\right)=k\le 4$ and $N\left(v_1\right)=\{u_1,u_2,\dots ,u_{k-1},v\}$. Then, $G-v{v}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i-1$ for $i\in [2,9]$. By Claim 3, we discuss two cases as follows.

Case 1.$d_k\left(v_1\right)=0$. Without a loss of generality, suppose that $\varphi \left(v_1{u}_j\right)=a_j\in [1,8+j]\subseteq [1,7+k]$ for $j\in [1,k-1]$. Firstly, $v{v}_1$ is colored with any color in $[8+k,13]$. Secondly, for each $v_i$ with $d\left(v_i\right)\le 4$ and $i\ge 2$, by Claim 3, $v_i$ has at most one conflicting vertex. We recolor $v{v}_i$ with a color $b_i\in [9,13]\backslash C_{\varphi }\left(v_i\right)$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$, and we color $v{v}_1$ with a color in $[8+k,13]\backslash \left\{b_i\right\}$. We can find at least $(6-k)+(d_{4^{-}}\left(v\right)-1)(5-k)=(5-k)d_{4^{-}}\left(v\right)+1$ different ways to recolor or color some edges incident with v. As v has at most $(5-k)d_{4^{-}}\left(v\right)$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

Case 2.$d_k\left(v_1\right)=1$, that is, $d\left(u_{k-1}\right)=d\left(v_1\right)=k$. By Claim 3, we can conclude that each vertex in $(N\left(v_1\right)\cup N\left(u_{k-1}\right))\backslash \{v_1,u_{k-1}\}$ is a $7^{+}$-vertex in G. We recolor $v_1{u}_{k-1}$ with a color in $[1,8]\backslash (C_{\varphi }\left(v_1\right)\cup C_{\varphi }\left(u_{k-1}\right))$. Let $a\in C_{\varphi }\left(u_{k-1}\right)\backslash C_{\varphi }\left(v_1\right)$. We notice that if $v{v}_1$ can be colored with some color in $[9,13]\backslash \{a,\varphi \left(v_1{u}_1\right)$, $\dots ,\varphi \left(v_1{u}_{k-2}\right)\}$, then $u_{k-1}$ and $v_1$ do not conflict with each other. Without loss of generality, suppose that $\{a,\varphi \left(v_1{u}_1\right),\dots ,\varphi \left(v_1{u}_{k-2}\right)\}\subseteq [1,7+k]$. By a similar argument to Case 1, we may extend $\varphi$ to G, which is a contradiction. □

Claim 7. 

Let $v\in V\left(G\right)$ with $d\left(v\right)=10$.

(1) 

If $d_{k^{-}}\left(v\right)\ge 1$, then $d_{6^{+}}\left(v\right)\ge (4-k)d_{4^{-}}\left(v\right)+1$ for $k\in [1,3]$.

(2) 

If v is adjacent to a $T_1^2$-3-vertex, then $d_{6^{+}}\left(v\right)\ge d_{3^{-}}\left(v\right)+3$.

Proof. 

$\left(1\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le (4-k)d_{4^{-}}\left(v\right)$. Let us say that $d\left(v_1\right)=k\le 3$ and $N\left(v_1\right)=\{u_1,u_2,\dots ,u_{k-1},v\}$. Then, $G-v{v}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i-1$ for $i\in [2,10]$. By Claim 3, we discuss two cases as follows.

Remark 1. 

If $d\left(v_2\right)\le 3$, or $d\left(v_2\right)=4$ and $d_4\left(v_2\right)=0$, then $v{v}_2$ is recolored with a color $b_2\in [10,13]\backslash C_{\varphi }\left(v_2\right)$ such that $v_2$ does not conflict with the vertices adjacent to $v_2$. If $d\left(v_2\right)=4$ and $d_4\left(v_2\right)=1$, assuming $x_2\in N\left(v_2\right)$ with $d\left(x_2\right)=d\left(v_2\right)=4$, then $v_2{x}_2$ is recolored with a color in $[1,9]\backslash (C_{\varphi }\left(v_2\right)\cup C_{\varphi }\left(x_2\right))$. Let ${\alpha }_2\in C_{\varphi }\left(x_2\right)\backslash C_{\varphi }\left(v_2\right)$. Then, $v{v}_2$ is recolored with a color $b_2\in [10,13]\backslash ((C_{\varphi }\left(v_2\right)\backslash \{\varphi \left(v_2{x}_2\right),\varphi \left(v{v}_2\right)\})\cup \left\{{\alpha }_2\right\})$. Hence, there exists a color $b_2\in [10,13]$ such that if $v{v}_2$ is recolored with $b_2$, then $v_2$ does not conflict with the vertices adjacent to $v_2$.

Case 1.$d_k\left(v_1\right)=0$. Without loss of generality, suppose that $\varphi \left(v_1{u}_j\right)=a_j\in [1,9+j]\subseteq [1,8+k]$ for $j\in [1,k-1]$. Firstly, $v{v}_1$ is colored with any color in $[9+k,13]$. Secondly, for each $v_i$ with $d\left(v_i\right)\le 4$ and $i\ge 2$, by Claim 3, $v_i$ has at most one conflicting vertex. According to Remark 1, we recolor $v{v}_i$ with a color $b_i\in [10,13]$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$, and color $v{v}_1$ with a color in $[9+k,13]\backslash \left\{b_i\right\}$. We can find at least $(5-k)+(d_{4^{-}}\left(v\right)-1)(4-k)=(4-k)d_{4^{-}}\left(v\right)+1$ different ways to recolor or color some edges incident with v. Because v has at most $(4-k)d_{4^{-}}\left(v\right)$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

Case 2.$d_k\left(v_1\right)=1$, that is, $d\left(u_{k-1}\right)=d\left(v_1\right)=k$. By Claim 3, we can conclude that each vertex in $(N\left(v_1\right)\cup N\left(u_{k-1}\right))\backslash \{v_1,u_{k-1}\}$ is a $7^{+}$-vertex in G. We recolor $v_1{u}_{k-1}$ with a color in $[1,9]\backslash (C_{\varphi }\left(v_1\right)\cup C_{\varphi }\left(u_{k-1}\right))$. Let $a\in C_{\varphi }\left(u_{k-1}\right)\backslash C_{\varphi }\left(v_1\right)$. We notice that if $v{v}_1$ can be colored with some color in $[10,13]\backslash \{a,\varphi \left(v_1{u}_1\right)$, $\dots ,\varphi \left(v_1{u}_{k-2}\right)\}$, then $u_{k-1}$ and $v_1$ do not conflict with each other. Without loss of generality, suppose that $\{a,\varphi \left(v_1{u}_1\right),\dots ,\varphi \left(v_1{u}_{k-2}\right)\}$$\subseteq [1,8+k]$. By a similar argument to Case 1, we may extend $\varphi$ to G, which is a contradiction.

$\left(2\right)$ Suppose that $v_1$ is a $T_1^2$-3-vertex. By Claim 5(1), we can conclude that v is not in any bad 3-cycle. Let $N\left(v_1\right)=\{v,v_2,u_1\}$ and $N\left(u_1\right)=\{v_1,v_2,x\}$. Then, $u_1\notin N\left(v\right)$. Assume to the contrary that $d_{6^{+}}\left(v\right)\le d_{3^{-}}\left(v\right)+2$. Then, $G-v_1{u}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,10]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(u_1\right)$, then $v_1{u}_1$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(u_1\right)=\{1,a\}$, that is, $\varphi \left(v_1{v}_2\right)=\varphi \left(u_{1}x\right)=a$ and $\varphi \left(v_2{u}_1\right)=1$. We deal with the following two possibilities in terms of symmetry.

• $a\in [1,10]$. Firstly, we recolor $v{v}_1$ with any color in $[11,13]$. Secondly, we exchange the colors of $v{v}_2$ and $v_2{u}_1$, and recolor $v{v}_1$ with any color in $[11,13]$. Thirdly, for each $v_i$ with $d\left(v_i\right)\le 3$ and $i\ge 3$, we recolor $v{v}_i$ with a color $b_i\in \{1,11-13\}$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$, and $v{v}_1$ with any color in $[11,13]\backslash \left\{b_i\right\}.$ We can find at least $6+2(d_{3^{-}}\left(v\right)-1)=2d_{3^{-}}\left(v\right)+4$ different ways to recolor the edges incident with v. Because v has at most $d_{3^{-}}\left(v\right)+2$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.
• $a\notin [1,10]$, say $a=11$. Firstly, we recolor $v{v}_1$ with any color in $[12,13]$. Secondly, we exchange the colors of $v{v}_2$ and $v_1{v}_2$, and recolor $v{v}_1$ with any color in $[12,13]$. Thirdly, for each $v_i$ with $d\left(v_i\right)\le 3$ and $i\ge 3$, we recolor $v{v}_i$ with a color $b_i\in \{1,11-13\}$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$, and $v{v}_1$ with any color in $[12,13]\backslash \left\{b_i\right\}.$ We can find at least $4+(d_{3^{-}}\left(v\right)-1)=d_{3^{-}}\left(v\right)+3$ different ways to recolor the edges incident with v. As v has at most $d_{3^{-}}\left(v\right)+2$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

□

Claim 8. 

Let $v\in V\left(G\right)$ with $d\left(v\right)=11$.

(1) 

If $d_1\left(v\right)\ge 1$ and $d_{3^{-}}\left(v\right)\ge 2$, then $d_{6^{+}}\left(v\right)\ge 2d_{4^{-}}\left(v\right)+1$.

(2) 

If $d_{2^{-}}\left(v\right)\ge 1$, then $d_{6^{+}}\left(v\right)\ge d_{3^{-}}\left(v\right)+1$.

(3) 

If v is in a bad 3-cycle, then $d_{6^{+}}\left(v\right)\ge 2d_{4^{-}}\left(v\right)+1$.

(4) 

If v is in a $(4,4,11)$-cycle and $d_{3^{-}}\left(v\right)\ge 1$, then $d_{6^{+}}\left(v\right)\ge 6$.

(5) 

If v is adjacent to a $T_1^2$-3-vertex, then $d_{6^{+}}\left(v\right)\ge d_{3^{-}}\left(v\right)+3$.

Proof. 

$\left(1\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le 2d_{4^{-}}\left(v\right)$. Let us say that $d\left(v_1\right)=1$ and $d\left(v_2\right)\le 3$. Then $G-v{v}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i-1$ for $i\in [2,11]$.

Firstly, $v{v}_1$ is colored with any color in $[11,13]$. Secondly, by Claim 3, $v_2$ has at most one conflicting vertex. By a similar argument to Remark 1 in Claim 7(1), we recolor $v{v}_2$ with a color $b_2\in [11,13]$ such that $v_2$ does not conflict with the vertices adjacent to $v_2$, and color $v{v}_1$ with any color in $[11,13]\backslash \left\{b_2\right\}$. Thirdly, for each $v_i$ with $d\left(v_i\right)\le 4$ and $i\ge 3$, by Claim 3, $v_i$ has at most one conflicting vertex. According to Remark 1 in Claim 7(1), $v{v}_i$ is recolored with a color $b_i\in \{1,11-13\}$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$. If $b_i\in [11,13]$, then $v{v}_1$ is colored with any color in $[11,13]\backslash \left\{b_i\right\}$. If $b_i=1$, then we recolor $v{v}_2$ with $b_2\in [11,13]$ and color $v{v}_1$ with any color in $[11,13]\backslash \left\{b_2\right\}$. We can find at least $3+2(d_{4^{-}}\left(v\right)-1)=2d_{4^{-}}\left(v\right)+1$ different ways to recolor or color some edges incident with v. Because v has at most $2d_{4^{-}}\left(v\right)$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

$\left(2\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le d_{3^{-}}\left(v\right)$. Let $d\left(v_1\right)\le 2$ and x be the neighbor of $v_1$ different from v (if it exists). Then, $G-v{v}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i-1$ for $i\in [2,11]$. Suppose that $\varphi \left(v_{1}x\right)\in [1,11]$, if x exists.

Firstly, $v{v}_1$ is colored with any color in $[12,13]$. Secondly, for each $v_i$ with $d\left(v_i\right)\le 3$ and $i\ge 2$, by Claim 3, $v_i$ has at most one conflicting vertex. By a similar argument to Remark 1 in Claim $7\left(1\right)$, $v{v}_i$ is recolored with a color $b_i\in [11,13]$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$. Then, $v{v}_1$ is colored with a color in $[12,13]\backslash \left\{b_i\right\}$. We can find at least $2+(d_{3^{-}}\left(v\right)-1)=d_{3^{-}}\left(v\right)+1$ different ways to recolor or color some edges incident with v. As v has at most $d_{3^{-}}\left(v\right)$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

$\left(3\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le 2d_{4^{-}}\left(v\right).$ Let $v_1{v}_2\in E\left(G\right)$ with $d\left(v_1\right)=d\left(v_2\right)=3$. Then, $G-v_1{v}_2$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,11]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(v_2\right)$, then $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(v_2\right)=\{1,2\}$.

Firstly, $v{v}_1$ or $v{v}_2$ is recolored with any color in $[12,13]$. Secondly, we recolor $v{v}_1$ with 12 and $v{v}_2$ with 13. Thirdly, for each $v_i$ with $d\left(v_i\right)\le 4$ and $i\ge 3$, by Claim 3, $v_i$ has at most one conflicting vertex. According to Remark 1 in Claim 7(1), $v{v}_i$ is recolored with a color $b_i\in \{1,2,12,13\}$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$. If $b_i=j\in [1,2]$, then $v{v}_j$ is recolored with any color in $[12,13]$. If $b_i\in [12,13]$, then $v{v}_1$ or $v{v}_2$ is recolored with $[12,13]\backslash \left\{b_i\right\}$. We can find at least $5+2(d_{4^{-}}\left(v\right)-2)=2d_{4^{-}}\left(v\right)+1$ different ways to recolor some edges incident with v. As v has at most $2d_{4^{-}}\left(v\right)$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

$\left(4\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le 5.$ Let $v_1{v}_2\in E\left(G\right)$ with $d\left(v_1\right)=d\left(v_2\right)=4$ and $d\left(v_3\right)\le 3$. Then, $G-v_1{v}_2$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,11]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(v_2\right)$, then $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(v_2\right)$$=\{1,2,\alpha \}$. Let us deal with the following two possibilities according to symmetry.

• $\alpha \in [1,11]$. Firstly, we recolor $v{v}_1$ or $v{v}_2$ with any color in $[12,13]$. Secondly, we recolor $v{v}_1$ with 12 and $v{v}_2$ with 13. Thirdly, $v{v}_3$ is recolored with a color $\gamma \in \{1,2,12,13\}$ such that $v_3$ does not conflict with the vertices adjacent to $v_3$. If $\gamma =i\in \{1,2\},$ then $v{v}_i$ is recolored with 12 or 13. If $\gamma \in [12,13]$, then $v{v}_1$ or $v{v}_2$ is recolored with $[12,13]\backslash \left\{\gamma \right\}$. We can find at least seven different ways to recolor some edges incident with v. As v has at most five conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.
• $\alpha \notin [1,11]$, say $\alpha =12$. By a similar argument to Remark 1 in Claim 7(1), $v{v}_3$ is recolored with a color $\beta \in \{1,2,12\}$ such that $v_3$ does not conflict with the vertices adjacent to $v_3$. If $\beta =i\in \{1,2\},$ then we recolor $v{v}_i$ with 3 and color $v_1{v}_2$ properly to obtain an NDE-13-coloring of G. Otherwise, $\beta =12$. Firstly, we recolor $v{v}_3$ with 3 and $v{v}_1$ or $v{v}_2$ with 13. Secondly, for each $v_i$ with $i\in [1,2]$, we recolor $v{v}_3$ with 12 and $v{v}_i$ with 3 or 13. We can find at least six different ways to recolor some edges incident with v. As v has at most five conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

$\left(5\right)$ Suppose that $v_1$ is a $T_1^2$-3-vertex. If v is in a bad 3-cycle, by Claim 8(3), then $d_{3^{-}}\left(v\right)\ge 2$ and $d_{6^{+}}\left(v\right)\ge 2d_{4^{-}}\left(v\right)+1\ge d_{3^{-}}\left(v\right)+3$. So, we suppose that v is not in any bad 3-cycle. Let $N\left(v_1\right)=\{v,v_2,u_1\}$ and $N\left(u_1\right)=\{v_1,v_2,x\}$. Then, $u_1\notin N\left(v\right)$. Assume to the contrary that $d_{6^{+}}\left(v\right)\le d_{3^{-}}\left(v\right)+2$. Then, $G-v_1{u}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,11]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(u_1\right)$, then $v_1{u}_1$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(u_1\right)=\{1,a\}$, that is, $\varphi \left(v_1{v}_2\right)=\varphi \left(u_{1}x\right)=a$ and $\varphi \left(v_2{u}_1\right)=1$. On the basis of symmetry, we consider the following two possibilities.

• $a\in [1,11]$. Firstly, we recolor $v{v}_1$ with any color in $[12,13]$. Secondly, we exchange the colors of $v{v}_2$ and $v_2{u}_1$, and recolor $v{v}_1$ with any color in $[12,13]$. Thirdly, for each $v_i$ with $d\left(v_i\right)\le 3$ and $i\ge 3$, by a similar argument to Remark 1 in Claim 7(1), we recolor $v{v}_i$ with a color $b_i\in \{1,12,13\}$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$, and $v{v}_1$ with any color in $[12,13]\backslash \left\{b_i\right\}.$ We can find at least $4+(d_{3^{-}}\left(v\right)-1)=d_{3^{-}}\left(v\right)+3$ different ways to recolor the edges incident with v. As v has at most $d_{3^{-}}\left(v\right)+2$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.
• $a\notin [1,11]$, say $a=12$. Firstly, we recolor $v{v}_1$ with 13. Secondly, we exchange the colors of $v{v}_2$ and $v_1{v}_2$, and recolor $v{v}_1$ with 1 or 13. Thirdly, we exchange the colors of $v{v}_2$ and $v_2{u}_1$, and recolor $v{v}_1$ with 13. Fourthly, for each $v_i$ with $d\left(v_i\right)\le 3$ and $i\ge 3$, by a similar argument to Remark 1 in Claim 7(1), $v{v}_i$ is recolored with a color $b_i\in \{1,12,13\}$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$. If $b_i\in \{1,12\}$, then $v{v}_1$ is recolored with 13. If $b_i=13$, then we exchange the colors of $v{v}_2$ and $v_1{v}_2$. We can find at least $4+(d_{3^{-}}\left(v\right)-1)=d_{3^{-}}\left(v\right)+3$ different ways to recolor the edges incident with v. As v has at most $d_{3^{-}}\left(v\right)+2$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

□

Claim 9. 

Let $v\in V\left(G\right)$ with $d\left(v\right)=12$.

(1) 

If $d_1\left(v\right)\ge 4$, then $d_{6^{+}}\left(v\right)\ge d_{5^{-}}\left(v\right)+1$.

(2) 

If v is in a bad 3-cycle, then $d_{6^{+}}\left(v\right)\ge 2$.

(3) 

If v is in a $(4,4,12)$-cycle and $d_1\left(v\right)\ge 1$, then $d_{3^{-}}\left(v\right)\le 1$.

(4) 

If v is adjacent to a $T_1^2$-3-vertex, then $d_1\left(v\right)=0$.

Proof. 

$\left(1\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le d_{5^{-}}\left(v\right)$. Let $d\left(v_i\right)=1$ for $i\in [1,4]$. Then, $G-v{v}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i-1$ for $i\in [2,12]$. Firstly, $v{v}_1$ is colored with any color in $[12,13]$. Secondly, for each $v_i$ with $i\in [2,4]$, we recolor $v{v}_i$ with 12 and color $v{v}_1$ with 13. Thirdly, for each $v_i$ with $d\left(v_i\right)\le 5$ and $i\ge 5$, by a similar argument to Remark 1 in Claim 7(1), $v{v}_i$ is recolored with a color $c_i\in \{1-3,12,13\}\backslash C_{\varphi }\left(v_i\right)$ such that $v_i$ does not conflict with the vertices adjacent to $v_i$. If $c_i=j\in [1,3]$, then we recolor $v{v}_{j+1}$ with 12 and color $v{v}_1$ with 13. If $c_i\in [12,13]$, then we color $v{v}_1$ with $\{12,13\}\backslash \left\{c_i\right\}$. We can find at least $2+(d_{5^{-}}\left(v\right)-1)=d_{5^{-}}\left(v\right)+1$ different ways to recolor or color some edges incident with v. As v has at most $d_{5^{-}}\left(v\right)$ conflicting vertices, we may extend $\varphi$ to G, which is a contradiction.

$\left(2\right)$ Assume to the contrary that $d_{6^{+}}\left(v\right)\le 1$. Let $v_1{v}_2\in E\left(G\right)$ with $d\left(v_1\right)=d\left(v_2\right)=3$. Then, $G-v_1{v}_2$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,12]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(v_2\right)$, then $v_1{v}_2$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(v_2\right)=\{1,2\}$. We recolor $v{v}_1$ or $v{v}_2$ with 13. We can find at least two different ways to recolor some edges incident with v. As v has at most one conflicting vertex, we may extend $\varphi$ to G, which is a contradiction.

$\left(3\right)$ Assume to the contrary that $d_{3^{-}}\left(v\right)\ge 2.$ Let $d\left(v_1\right)=1$, $d\left(v_2\right)\le 3$ and $v_3{v}_4\in E\left(G\right)$ with $d\left(v_3\right)=d\left(v_4\right)=4$. Then, $G-v_3{v}_4$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,12]$. If $C_{\varphi }\left(v_3\right)\ne C_{\varphi }\left(v_4\right)$, then $v_3{v}_4$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_3\right)=C_{\varphi }\left(v_4\right)$$=\{3,4,\alpha \}$. By Claim 3, we can conclude that $v_2$ has at most one conflicting vertex. If $\alpha \ne 1$, then we recolor $v{v}_3$ with 1 and $v{v}_1$ with 3. Otherwise, $\alpha =1$. By a similar argument to Remark 1 in Claim 7(1), $v{v}_2$ is recolored with a color $\beta \in \{1,3,4\}$ such that $v_2$ does not conflict with the vertices adjacent to $v_2$. If $\beta =1$, then we recolor $v{v}_3$ with 2 and $v{v}_1$ with 3. If $\beta =i\in \{3,4\}$, then $v{v}_i$ is recolored with 2. Finally, $v_3{v}_4$ is colored properly to obtain an NDE-13-coloring of G, which is a contradiction.

$\left(4\right)$ Assume to the contrary that $d_1\left(v\right)\ge 1$. Suppose that $v_1$ is a $T_1^2$-3-vertex. By Claim 5(1), we can conclude that v is not in any bad 3-cycle. Let $N\left(v_1\right)=\{v,v_2,u_1\}$, $N\left(u_1\right)=\{v_1,v_2,x\}$ and $d\left(v_3\right)=1$. Then, $u_1\notin N\left(v\right)$, and $G-v_1{u}_1$ admits an NDE-13-coloring $\varphi$ with $\varphi \left(v{v}_i\right)=i$ for $i\in [1,12]$. If $C_{\varphi }\left(v_1\right)\ne C_{\varphi }\left(u_1\right)$, then $v_1{u}_1$ is colored properly to obtain an NDE-13-coloring of G. We suppose that $C_{\varphi }\left(v_1\right)=C_{\varphi }\left(u_1\right)=\{1,\alpha \}$, that is, $\varphi \left(v_1{v}_2\right)=\varphi \left(u_{1}x\right)=\alpha$ and $\varphi \left(v_2{u}_1\right)=1$. If $\alpha \ne 3$, then we recolor $v{v}_1$ with 3 and $v{v}_3$ with 1. If $\alpha =3$, then we exchange the colors of $v{v}_2$ and $v_1{v}_2$, and recolor $v{v}_3$ with 2. Finally, $v_1{u}_1$ is colored properly to obtain an NDE-13-coloring of G, which is a contradiction. □

Let H be the graph gained from G after we remove all 1-vertices in G. We notice that $d_H\left(v\right)=d_G\left(v\right)$$-d_1^G\left(v\right)$. Then, H is a connected plane graph with $\delta \left(H\right)\ge 2$.

3.2. Discharging Analysis in H

To derive a contradiction, we need to implement discharging analysis in H. By Claim 1, we may conclude that H is 2-connected. By Claims 2-9, we show the relationship between $d_G\left(v\right)$ and $d_H\left(v\right)$ in

Table 1. There is the relationship between $d_G\left(v\right)$ and $d_H\left(v\right)$.

$d_G\left(v\right)$	$2\le d_G\left(v\right)\le 7$	8	9	10	11	12	13
$d_H\left(v\right)$	$=d_G\left(v\right)$	$\ge 6$	$\ge 8$	$\ge 8$	$\ge 8$	$\ge 7$	13

, and some structural properties of H, are given in Claim 10.

Claim 10. 

Let $v\in V\left(H\right)$.

(1) 

If $2\le d_H\left(v\right)\le 5$, then $d_H\left(v\right)=d_G\left(v\right)$. So, $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)$.

(2) 

If $d_H\left(v\right)=2$, then $d_{5^{-}}^H\left(v\right)=0$.

(3) 

If $d_H\left(v\right)=k\in [3,5]$, then $d_{5^{-}}^H\left(v\right)=d_k^H\left(v\right)\le 1$.

(4) 

If $d_H\left(v\right)=6$, then $d_{5^{-}}^H\left(v\right)=0$.

(5) 

Assume that $d_H\left(v\right)=7$. If $d_{4^{-}}^H\left(v\right)\ge 1$, then $d_{5^{-}}^H\left(v\right)\le 1$.

(6) 

Assume that $d_H\left(v\right)=8$. Then v is not in any bad 3-cycle. If $d_{4^{-}}^H\left(v\right)\ge 1$, then $d_{5^{-}}^H\left(v\right)\le 2$.

(7) 

Assume that $d_H\left(v\right)=9$. Then v is not in any bad 3-cycle. If $d_{3^{-}}^H\left(v\right)\ge 1$, then $d_{6^{+}}^H\left(v\right)\ge 2d_{4^{-}}^H\left(v\right)+1$. If $d_{4^{-}}^H\left(v\right)\ge 1$, then $d_{6^{+}}^H\left(v\right)\ge d_{4^{-}}^H\left(v\right)+1$.

(8) 

Assume that $d_H\left(v\right)=10$. Then v is not in any bad 3-cycle. If $d_{3^{-}}^H\left(v\right)\ge 1$, then $d_{6^{+}}^H\left(v\right)\ge d_{4^{-}}^H\left(v\right)+1$. If v is adjacent to a $T_1^2$-3-vertex, then $d_{6^{+}}^H\left(v\right)\ge d_{3^{-}}^H\left(v\right)+3$.

(9) 

Assume that $d_H\left(v\right)=11$. If v is in a bad 3-cycle, then $d_{6^{+}}^H\left(v\right)\ge 2d_{4^{-}}^H\left(v\right)+1$. If $d_2^H\left(v\right)\ge 1$, then $d_{6^{+}}^H\left(v\right)\ge d_{3^{-}}^H\left(v\right)+1$. If v is in a $(4,4,11)$-cycle and $d_{3^{-}}^H\left(v\right)\ge 1$, then $d_{6^{+}}^H\left(v\right)\ge 6$. If v is adjacent to a $T_1^2$-3-vertex, then $d_{6^{+}}^H\left(v\right)\ge d_{3^{-}}^H\left(v\right)+3$.

(10) 

Assume that $d_H\left(v\right)=12$. If v is in a bad 3-cycle, then $d_{6^{+}}^H\left(v\right)\ge 2$.

Proof. 

Statements $\left(1\right)$, $\left(2\right)$, $\left(3\right)$ and $\left(10\right)$ hold clearly by Table 1 and Claims 3 and 9.

$\left(4\right)$ It is trivial when $d_G\left(v\right)=d_H\left(v\right)$. If $d_G\left(v\right)>d_H\left(v\right)$, then $d_G\left(v\right)=8$ by Table 1. If $d_G\left(v\right)=8$, then $d_1^G\left(v\right)=2$. By Claim 3(4), $d_{5^{-}}^G\left(v\right)\le 2$, which means that $d_{5^{-}}^H\left(v\right)=d_{5^{-}}^G\left(v\right)-d_1^G\left(v\right)=0$.

$\left(5\right)$ It is trivial when $d_G\left(v\right)=d_H\left(v\right)$. If $d_G\left(v\right)>d_H\left(v\right)$, then $d_G\left(v\right)=8$ or $d_G\left(v\right)=12$ by Table 1. If $d_G\left(v\right)=8$, then $d_1^G\left(v\right)=1$. By Claim 3(4), $d_{5^{-}}^G\left(v\right)\le 2$, which means that $d_{5^{-}}^H\left(v\right)=d_{5^{-}}^G\left(v\right)-d_1^G\left(v\right)\le 1$. If $d_G\left(v\right)=12$, then $d_1^G\left(v\right)=5$. By Claim 4(1), $d_s^G\left(v\right)=0$ for $s\in [2,5]$, which means that $d_{5^{-}}^H\left(v\right)=0$.

$\left(6\right)$ It is trivial when $d_G\left(v\right)=d_H\left(v\right)$. If $d_G\left(v\right)>d_H\left(v\right)$, then $d_1^G\left(v\right)\ge 1$ and $d_G\left(v\right)\in [9,12]$. By Claim 5(1), v is not in any bad 3-cycle in H. If $d_G\left(v\right)=9$, then $d_1^G\left(v\right)=1$. By Claim 6(1), $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)\ge 4d_{4^{-}}^G\left(v\right)+1=4d_{4^{-}}^H\left(v\right)+5$, which means that $d_{4^{-}}^H\left(v\right)=0$. If $d_G\left(v\right)=10$, then $d_1^G\left(v\right)=2$. By Claim 7(1), $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)\ge 3d_{4^{-}}^G\left(v\right)+1=3d_{4^{-}}^H\left(v\right)+7$, which means that $d_{4^{-}}^H\left(v\right)=0$. If $d_G\left(v\right)\in \{11,12\}$, then $d_1^G\left(v\right)\ge 3$. By Claim 4(1), $d_s^G\left(v\right)=0$ for $s\in [2,4]$, which means that $d_{4^{-}}^H\left(v\right)=0$.

$\left(7\right)$ It is trivial when $d_G\left(v\right)=d_H\left(v\right)$. If $d_G\left(v\right)>d_H\left(v\right)$, then $d_1^G\left(v\right)\ge 1$ and $d_G\left(v\right)\in [10,12]$. By Claim 5(1), v is not in any bad 3-cycle in H. If $d_G\left(v\right)=10$, then $d_1^G\left(v\right)=1$. By Claim 7(1), $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)\ge 3d_{4^{-}}^G\left(v\right)+1=3d_{4^{-}}^H\left(v\right)+4$, which means that $d_{4^{-}}^H\left(v\right)\le 1$. If $d_G\left(v\right)=11$, then $d_1^G\left(v\right)=2$. By Claim 8(1), $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)\ge 2d_{4^{-}}^G\left(v\right)+1=2d_{4^{-}}^H\left(v\right)+5$, which means that $d_{4^{-}}^H\left(v\right)\le 1$. If $d_G\left(v\right)=12$, then $d_1^G\left(v\right)=3$. By Claim 4(1), $d_s^G\left(v\right)=0$ for $s\in [2,4]$, which means that $d_{4^{-}}^H\left(v\right)=0$.

$\left(8\right)$ It is trivial when $d_G\left(v\right)=d_H\left(v\right)$. If $d_G\left(v\right)>d_H\left(v\right)$, then $d_1^G\left(v\right)\ge 1$ and $d_G\left(v\right)\in [11,12]$. By Claim 5(1), v is not in any bad 3-cycle in H. Assume that $d_G\left(v\right)=11$. Then, $d_1^G\left(v\right)=1$. If $d_{3^{-}}^H\left(v\right)\ge 1$, meaning $d_{3^{-}}^G\left(v\right)\ge 2$, by Claim 8(1), then $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)\ge 2d_{4^{-}}^G\left(v\right)+1\ge 2d_{4^{-}}^H\left(v\right)+3$. If v is adjacent to a $T_1^2$-3-vertex, meaning $d_{3^{-}}^G\left(v\right)\ge 2$, by Claim 8(1), then $d_{6^{+}}^H\left(v\right)=d_{6^{+}}^G\left(v\right)\ge 2d_{4^{-}}^G\left(v\right)+1\ge 2d_{3^{-}}^G\left(v\right)+1\ge 2d_{3^{-}}^H\left(v\right)+3$. Assume that $d_G\left(v\right)=12$. Then, $d_1^G\left(v\right)=2$. By Claim 4(1), $d_s^G\left(v\right)=0$ for $s\in [2,3]$, which means that $d_{3^{-}}^H\left(v\right)=0$.

$\left(9\right)$ It is trivial when $d_G\left(v\right)=d_H\left(v\right)$. If $d_G\left(v\right)>d_H\left(v\right)$, then $d_1^G\left(v\right)=1$ and $d_G\left(v\right)=12$. By Claim 5(1), v is not in any bad 3-cycle in H. By Claim 9(4), v is not adjacent to any $T_1^2$-3-vertex in H. By Claim 4(1), $d_2^G\left(v\right)=0$, which means that $d_2^H\left(v\right)=0$. If $d_{3^{-}}^H\left(v\right)\ge 1$, meaning $d_{3^{-}}^G\left(v\right)\ge 2$, by Claim 9(3), v is not in any $(4,4,12)$-cycle in G, which means that v is not in any $(4,4,11)$-cycle in H. □

By Euler’s formula $\left|V\right(H\left)\right|-\left|E\right(H\left)\right|+\left|F\right(H\left)\right|=2$, we have

$$\sum _{v\in V\left(H\right)}(d_H\left(v\right)-6)+\sum _{f\in F\left(H\right)}(2d_H\left(f\right)-6)=-12.$$

Firstly, we define an initial weight function $w\left(v\right)=d_H\left(v\right)-6$ for every vertex $v\in V\left(H\right)$ and $w\left(f\right)=2d_H\left(f\right)-6$ for every face $f\in F\left(H\right)$. Secondly, we design some discharging rules and redistribute weights accordingly. After discharge is complete, a new weight function $w^{\prime }$ is produced. When discharge is in process, the sum of all weights is kept fixed. However, we can prove that $w^{\prime }\left(x\right)\ge 0$ for all $x\in V\left(H\right)\cup F\left(H\right)$. This results in the following obvious contradiction:

$$0\le \sum _{x\in V\left(H\right)\cup F\left(H\right)}{w}^{\prime }\left(x\right)=\sum _{x\in V\left(H\right)\cup F\left(H\right)}w\left(x\right)=-12,$$

and, hence, demonstrates that there is no such counterexample.

The discharging rules are made as follows:

(R1) 

Let f be a 4-face. If $d_2^H\left(f\right)=1$, then f sends 2 to its incident 2-vertex. Otherwise, f sends 1 to each incident small vertex.

(R2) 

Let f be a $5^{+}$-face. Then, f sends 2 to each incident 2-vertex, and $\frac{\omega \left(f\right)-2d_2^H\left(f\right)}{d_3^H\left(f\right)+d_4^H\left(f\right)+d_5^H\left(f\right)}$ to each incident small vertex of a degree of at least 3.

For a small vertex u, we use $\beta \left(u\right)$ to denote the total sum of charges transferred into u after (R1)–(R2) was carried out.

(R3) 

Let v be a $7^{+}$-vertex adjacent to a small k-vertex u. If $d_k^H\left(u\right)=1$, then v sends max $\{\frac{6-d_H\left(u\right)-\beta \left(u\right)}{d_H\left(u\right)-1},0\}$ to u; if $d_k^H\left(u\right)=0$, then v sends max $\{\frac{6-d_H\left(u\right)-\beta \left(u\right)}{d_H\left(u\right)},0\}$ to u.

For $x,y\in V\left(H\right)\cup F\left(H\right)$, we use $\tau (x\to y)$ to denote the charge transferred from x to y on the basis of the above rules.

Observation 1. 

(Wang et al. [13]) Suppose that $f\in F\left(H\right)$, and v is a small vertex incident with f.

(1) 

Every face f is incident with at most $\lfloor \frac{2d_H\left(f\right)}{3}\rfloor$ small vertices.

(2) 

Let $d_H\left(f\right)=5$. If $d_2^H\left(f\right)\ge 1$, then $\tau (f\to v)\ge 1$. Otherwise, $\tau (f\to v)\ge \frac{4}{3}$.

(3) 

Let $d_H\left(f\right)=6$. If $d_2^H\left(f\right)\ge 1$, then $\tau (f\to v)\ge 2$. Otherwise, $\tau (f\to v)\ge \frac{3}{2}$.

(4) 

Let $d_H\left(f\right)\ge 7$. Then, $\tau (f\to v)\ge 2$.

Observation 2. 

Suppose that $v\in V\left(H\right)$ is a $7^{+}$-vertex, u is a small vertex adjacent to v and $G_1$ is the configuration of Figure 1.

(1) 

Assume that $d_H\left(u\right)=2$. If v is in a special 3-face, then $\tau (v\to u)\le 1$. Otherwise, $\tau (v\to u)=0$.

(2) 

Assume that $d_H\left(u\right)=3$. If v is in $G_1$, then $\tau (v\to u)\le \frac{3}{2}$. Otherwise, $\tau (v\to u)\le 1$.

(3) 

Assume that $d_H\left(u\right)=4$. Then, $\tau (v\to u)\le \frac{2}{3}$.

(4) 

Assume that $d_H\left(u\right)=5$. Then, $\tau (v\to u)\le \frac{1}{4}$.

(5) 

If v is in a bad 3-face, and u is not in this bad 3-face, then $\tau (v\to u)\le \frac{1}{2}$.

(6) 

If v is in $G_1$, and u is not in $G_1$, then $\tau (v\to u)\le \frac{1}{3}$.

(7) 

If v is in a special 3-face and $u\in N_3^H\left(v\right)$, then $\tau (v\to u)\le \frac{2}{3}$.

Proof. 

$\left(1\right)-\left(6\right)$ has been proved in [13], and we only need to prove $\left(7\right)$. If v is in a special 3-face, by Claim 4(4), then $d_2^H\left(v\right)=1$. According to the nonexistence of $G_4$ in Claim 5(3), one of the faces incident with $uv$ is at least a 4-face without 2-vertex or $5^{+}$-face. By (R1) and Observation 1, we can conclude that $\beta \left(u\right)\ge 1$. If $d_3^H\left(u\right)=0$, then $\tau (v\to u)\le \frac{6-3-1}{3}=\frac{2}{3}$. If $d_3^H\left(u\right)=1$, by Claim 5(1), then two of the faces incident with u are at least 4-faces without 2-vertices or $5^{+}$-faces. By (R1) and Observation 1, we have $\beta \left(u\right)\ge 2$. Hence, $\tau (v\to u)\le \frac{6-3-2}{3-1}=\frac{1}{2}$. □

Observation 3. 

Let $v\in V\left(H\right)$ be an $8^{+}$-vertex that is not in any bad 3-face, and $v_i,v_{i+1},v_{i+2},\dots$, $v_{i+s},v_{i+s+1}$ be $s+2$ consecutive neighbors of v. If $d_H\left(v_{i+j}\right)\in [3,5]$ for $j\in [1,s]$ and $s\ge 2$, then ${\displaystyle \sum _{j=1}^s}\tau (v\to v_{i+j})\le \frac{s}{3}+1$. Further,

(1) 

If neither $v_{i+1}$ nor $v_{i+s}$ is in a bad 3-face, then ${\displaystyle \sum _{j=1}^s}\tau (v\to v_{i+j})\le \frac{s}{3}+\frac{2}{3}$.

(2) 

If exactly one of $v_{i+1}$ and $v_{i+s}$ is in a bad 3-face, then ${\displaystyle \sum _{j=1}^s}\tau (v\to v_{i+j})\le \frac{s}{3}+\frac{5}{6}$.

(3) 

If $s=2$ and $d_H\left(v_i\right),d_H\left(v_{i+3}\right)\notin [3,5]$, then $\tau (v\to v_{i+1})+\tau (v\to v_{i+2})\le \frac{3}{2}$.

(4) 

If $s=3$ and $d_H\left(v_{i+j}\right)\in [4,5]$ for $j\in [1,3]$, then ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{4}{3}$.

(5) 

If $s=3$ and $d_H\left(v_{i+j}\right)=5$ for $j\in [1,3]$, then ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{1}{4}$.

Proof. 

$\left(1\right)-\left(3\right)$ has been proved in [13], and we only need to prove $\left(4\right)$ and $\left(5\right)$. If there are three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_{4,5}^H\left(v\right)$, then one of the faces incident with $v{v}_{i+2}$ is at least a 4-face without 2-vertex or $5^{+}$-face by Claim 10(3). Hence, ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{6-4-0}{4-1}+\frac{6-4-1}{4-1}+\frac{6-4-1}{4-1}=\frac{4}{3}$ by (R1) and Observation 1. Similarly, if there are three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_5^H\left(v\right)$, then one of the faces incident with $v{v}_{i+2}$ is at least a 4-face without 2-vertex or $5^{+}$-face by Claim 10(3). Hence, ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{6-5-0}{5-1}+\frac{6-5-1}{5-1}+\frac{6-5-1}{5-1}=\frac{1}{4}$ by (R1) and Observation 1. □

Suppose that $f\in F\left(H\right)$. If $d_H\left(f\right)=3$, then ${\omega }^{\prime }\left(f\right)=\omega \left(f\right)=2\times 3-6=0$. If $d_H\left(f\right)=4$, then f is incident with at most two $5^{-}$-vertices by Observation 1. By Claim 4(3) and (R1), f sends at most 2 to all its incident small vertices. Hence, ${\omega }^{\prime }\left(f\right)\ge \omega \left(f\right)-2=2\times 4-6-2=0$. If $d_H\left(f\right)\ge 5$, by (R2), then

$${\omega }^{\prime }\left(f\right)\ge \omega \left(f\right)-2d_2^H\left(f\right)-\frac{\omega \left(f\right)-2d_2^H\left(f\right)}{d_3^H\left(f\right)+d_4^H\left(f\right)+d_5^H\left(f\right)}(d_3^H\left(f\right)+d_4^H\left(f\right)+d_5^H\left(f\right))=0.$$

Suppose that $v\in V\left(H\right)$ is a k-vertex. Then, $k\ge 2$. We use $v_0,v_1,\dots ,v_{k-1}$ to denote the vertices adjacent to v in clockwise order. For $0\le i\le k-1$, $f_i$ is used to denote the incident face of v in H with $v{v}_i$ and $v{v}_{i+1}$ as boundary edges, where all indices are taken modulo k. If $k=6$, by (R3) and Claim 10(4), then ${\omega }^{\prime }\left(v\right)=\omega \left(v\right)=6-6=0$.

Case 1.$k\in [2,5]$. If $d_k^H\left(v\right)=1$, then $d_{6^{-}}^H\left(v\right)=1$ by Claim 10(1)–(4). Hence, by (R1)–(R3), ${\omega }^{\prime }\left(v\right)\ge k-6+\beta \left(v\right)+\frac{6-k-\beta \left(v\right)}{k-1}\times (k-1)=0$. If $d_k^H\left(v\right)=0$, by Claim 10(1)–(4), then $d_{6^{-}}^H\left(v\right)=0$. Hence, by (R1)–(R3), ${\omega }^{\prime }\left(v\right)\ge k-6+\beta \left(v\right)+\frac{6-k-\beta \left(v\right)}{k}\times k=0$.

Case 2.$k=7$. Then, $\omega \left(v\right)=1$. If $d_{4^{-}}^H\left(v\right)\ge 1$, by Claim 10(5), then $d_{5^{-}}^H\left(v\right)\le 1$. Then, v is not in any bad 3-face. Hence, by Observation 2(1)–(3), ${\omega }^{\prime }\left(v\right)\ge 1-d_{5^{-}}^H\left(v\right)\ge 1-1=0$. Otherwise, $d_{4^{-}}^H\left(v\right)=0$. If $d_{6^{+}}^H\left(v\right)\ge 3$, by Observation 2(4), then ${\omega }^{\prime }\left(v\right)\ge 1-\frac{1}{4}\times (7-d_{6^{+}}^H\left(v\right))=\frac{1}{4}{d}_{6^{+}}^H\left(v\right)-\frac{3}{4}\ge 0$. If $d_{6^{+}}^H\left(v\right)=2$, then there exist three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_5^H\left(v\right)$. Hence, $\sum _{j=1}^3\tau (v\to v_{i+j})\le \frac{1}{4}$ by Observation 3(5) and ${\omega }^{\prime }\left(v\right)\ge 1-\frac{1}{4}-\frac{1}{4}\times (7-3-2)=\frac{1}{4}$ by Observation 2(4). If $d_{6^{+}}^H\left(v\right)\le 1$, then there are two vertex-disjoint subsets $\{v_{i+1},v_{i+2},v_{i+3}\},\{v_{m+1},v_{m+2},v_{m+3}\}\subseteq N_5^H\left(v\right)$, and then ${\omega }^{\prime }\left(v\right)\ge 1-\frac{1}{4}\times 2-\frac{1}{4}\times (7-3-3-d_{6^{+}}^H\left(v\right))=\frac{1}{4}{d}_{6^{+}}^H\left(v\right)+\frac{1}{4}\ge \frac{1}{4}$ by Observations 2 and 3.

Case 3.$k=8$. Then, $\omega \left(v\right)=2$. By Claim 10(6), v is not in any bad 3-face. If $d_{4^{-}}^H\left(v\right)\ge 1$, then $d_{5^{-}}^H\left(v\right)\le 2$ by Claim 10(6). Hence, by Observation 2(1)–(4), ${\omega }^{\prime }\left(v\right)\ge 2-d_{5^{-}}^H\left(v\right)\ge 2-1\times 2=0$. If $d_{4^{-}}^H\left(v\right)=0$, then ${\omega }^{\prime }\left(v\right)\ge 2-\frac{1}{4}{d}_5^H\left(v\right)\ge 2-\frac{1}{4}\times 8=0$ by Observation 2(4).

Case 4.$k=9$. Then, $\omega \left(v\right)=3$. By Claim 10(7), v is not in any bad 3-face. If $d_{3^{-}}^H\left(v\right)\ge 1$, by Claim 10(7), then $d_{6^{+}}^H\left(v\right)\ge 2d_{4^{-}}^H\left(v\right)+1$, which means that $d_{4^{-}}^H\left(v\right)\le 2$. Hence, by Observation 2(1)–(4), ${\omega }^{\prime }\left(v\right)\ge 3-d_{4^{-}}^H\left(v\right)-\frac{1}{4}(9-d_{4^{-}}^H\left(v\right)-d_{6^{+}}^H\left(v\right))\ge 1-\frac{1}{4}{d}_{4^{-}}^H\left(v\right)\ge \frac{1}{2}$. If $d_{3^{-}}^H\left(v\right)=0$ and $d_4^H\left(v\right)\ge 1$, by Claim 10(7), then $d_{6^{+}}^H\left(v\right)\ge d_4^H\left(v\right)+1$, which means that $d_4^H\left(v\right)\le 4$. Hence, by Observation 2(3)–(4), ${\omega }^{\prime }\left(v\right)\ge 3-\frac{2}{3}{d}_4^H\left(v\right)-\frac{1}{4}(9-d_4^H\left(v\right)-d_{6^{+}}^H\left(v\right))\ge 1-\frac{1}{6}{d}_4^H\left(v\right)\ge \frac{1}{3}$. If $d_{4^{-}}^H\left(v\right)=0$, by Observation 2(4), then ${\omega }^{\prime }\left(v\right)\ge 3-\frac{1}{4}{d}_5^H\left(v\right)\ge 3-\frac{1}{4}\times 9=\frac{3}{4}$.

Case 5.$k=10$. Then, $\omega \left(v\right)=4$. By Claim 10(8), v is not in any bad 3-face.

Case 5.1.$d_{3^{-}}^H\left(v\right)\ge 1$. By Claim 4(2), $d_2^H\left(v\right)\le 1$. By Claim 10(8), $d_{6^{+}}^H\left(v\right)\ge d_{4^{-}}^H\left(v\right)+1$, which means that $d_{4^{-}}^H\left(v\right)\le 4$. If $d_{4^{-}}^H\left(v\right)\le 3$, by Observation 2(1)–(4), then ${\omega }^{\prime }\left(v\right)\ge 4-d_{4^{-}}^H\left(v\right)-\frac{1}{4}(10-d_{4^{-}}^H\left(v\right)-d_{6^{+}}^H\left(v\right))\ge \frac{7}{4}-\frac{1}{2}{d}_{4^{-}}^H\left(v\right)\ge \frac{1}{4}$. If $d_{4^{-}}^H\left(v\right)=4$ and $d_{6^{+}}^H\left(v\right)=6$, then ${\omega }^{\prime }\left(v\right)\ge 4-d_{4^{-}}^H\left(v\right)=4-1\times 4=0$ by Observation 2(1)–(3). Otherwise, $d_{4^{-}}^H\left(v\right)=4$, $d_5^H\left(v\right)=1$ and $d_{6^{+}}^H\left(v\right)=5$.

If v is in a special 3-face, by Claim 4(4), then $d_2^H\left(v\right)=1$. Hence, ${\omega }^{\prime }\left(v\right)\ge 4-1-$$\frac{2}{3}\times (4-1)-\frac{1}{4}=\frac{3}{4}$ by Observation 2. Thus, we assume that v is not in any special 3-face. If $d_2^H\left(v\right)=1$, then ${\omega }^{\prime }\left(v\right)\ge 4-(4-1)-\frac{1}{4}=\frac{3}{4}$ by Observation 2(1)–(4). If $d_2^H\left(v\right)=0$ and $d_4^H\left(v\right)\ge 1$, then ${\omega }^{\prime }\left(v\right)\ge 4-(4-d_4^H\left(v\right))-\frac{2}{3}{d}_4^H\left(v\right)-\frac{1}{4}=\frac{1}{3}{d}_4^H\left(v\right)-\frac{1}{4}\ge \frac{1}{12}$ by Observation 2(1)–(4). Then, we suppose that $d_2^H\left(v\right)=d_4^H\left(v\right)=0$, $d_3^H\left(v\right)=4$, $d_5^H\left(v\right)=1$ and $d_{6^{+}}^H\left(v\right)=5$. By Claim 10(8), v is not adjacent to any $T_1^2$-3-vertex. For each $v_i\in N_3^H\left(v\right)$ with $d_3^H\left(v_i\right)=1$, $\tau (v\to v_i)\le \frac{6-3-2}{3-1}=\frac{1}{2}$. For each two consecutive vertices $v_{i+1},v_{i+2}\in N_{3,5}^H\left(v\right)$, $\sum _{j=1}^2\tau (v\to v_{i+j})\le \frac{6-3-1}{3}+\frac{6-3-1}{3}=\frac{4}{3}$ by (R1) and Observation 1.

If there exist two consecutive vertices $v_{i+1},v_{i+2}\in N_3^H\left(v\right)$, then ${\omega }^{\prime }\left(v\right)\ge 4-\frac{4}{3}-1\times (4-2)-\frac{1}{4}=\frac{5}{12}$ by Observation 2. If there are two consecutive vertices $v_{i+1},v_{i+2}$ with $v_{i+1}\in N_3^H\left(v\right)$ and $v_{i+2}\in N_5^H\left(v\right)$, then ${\omega }^{\prime }\left(v\right)\ge 4-\frac{6-3-1}{3}-\frac{6-5-1}{4}-1\times (4-1)=\frac{1}{3}$ by Observation 2. Otherwise, there are nine consecutive vertices $v_{i+1},v_{i+2},\dots ,v_{i+9}$ with $v_{i+2},v_{i+4},v_{i+6},v_{i+8}\in N_3^H\left(v\right)$ and $v_{i+1},v_{i+3},v_{i+5},v_{i+7},v_{i+9}\in N_{6^{+}}^H\left(v\right)$. By the nonexistence of $G_5$ in Claim 5(3), there are two subscripts $a,b\in \{i+2,i+4,i+6,i+8\}$ such that one of $f_{a-1}$ and $f_a$ is at least a 4-face without 2-vertex or $5^{+}$-face, and one of $f_{b-1}$ and $f_b$ is at least a 4-face without 2-vertex or $5^{+}$-face. Hence, by Observation 2, ${\omega }^{\prime }\left(v\right)\ge 4-\frac{6-3-1}{3}\times 2-1\times (4-2)-\frac{1}{4}=\frac{5}{12}$.

Case 5.2.$d_{3^{-}}^H\left(v\right)=0$. If $d_{6^{+}}^H\left(v\right)\ge 4$, by Observation 2(3)–(4), then ${\omega }^{\prime }\left(v\right)\ge 4-\frac{2}{3}(10-d_{6^{+}}^H\left(v\right))=\frac{2}{3}{d}_{6^{+}}^H\left(v\right)-\frac{8}{3}\ge 0$. If $d_{6^{+}}^H\left(v\right)\le 1$, by Observation 3(1), then ${\omega }^{\prime }\left(v\right)\ge 4-(\frac{10-d_{6^{+}}^H\left(v\right)}{3}+\frac{2}{3})=\frac{1}{3}{d}_{6^{+}}^H\left(v\right)\ge 0$. Otherwise, $2\le d_{6^{+}}^H\left(v\right)\le 3$.

• $d_{6^{+}}^H\left(v\right)=3$. Then, there are three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_{4,5}^H\left(v\right)$. Hence, ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{4}{3}$ by Observation 3(4) and ${\omega }^{\prime }\left(v\right)\ge 4-\frac{4}{3}-\frac{2}{3}\times (10-3-3)=0$ by Observation 2.
• $d_{6^{+}}^H\left(v\right)=2$. Then, there are two vertex-disjoint subsets $\{v_{i+1},v_{i+2},v_{i+3}\}$, $\{v_{m+1},v_{m+2}$, $v_{m+3}\}\in N_{4,5}^H\left(v\right)$. By Observation 3(4), ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{4}{3}$ and ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{m+j})\le \frac{4}{3}$. Hence, ${\omega }^{\prime }\left(v\right)\ge 4-\frac{4}{3}\times 2-\frac{2}{3}\times (10-2-3-3)=0$ by Observation 2.

Case 6.$k=11$. Then, $\omega \left(v\right)=5$. If v is in a bad 3-face, then $d_{6^{+}}^H\left(v\right)\ge 2d_{4^{-}}^H\left(v\right)+1\ge 5$ by Claim 10(9). Hence, ${\omega }^{\prime }\left(v\right)\ge 5-\frac{3}{2}\times 2-\frac{1}{2}\times (11-2-d_{6^{+}}^H\left(v\right))=\frac{1}{2}{d}_{6^{+}}^H\left(v\right)-\frac{5}{2}\ge 0$ by Observation 2. Thus, we assume that v is not in any bad 3-face.

Case 6.1.v is in a special 3-face. By Claim 4(4) and 10(9), $d_2^H\left(v\right)=1$ and $d_{6^{+}}^H\left(v\right)\ge d_{3^{-}}^H\left(v\right)+1\ge 2$. If $d_{6^{+}}^H\left(v\right)\ge 4$, then ${\omega }^{\prime }\left(v\right)\ge 5-1-\frac{2}{3}\times (11-1-d_{6^{+}}^H\left(v\right))=\frac{2}{3}{d}_{6^{+}}^H\left(v\right)-\frac{8}{3}\ge 0$ by Observation 2. Otherwise, $2\le d_{6^{+}}^H\left(v\right)\le 3$. By Claim 10(9), v is not in any $(4,4,11)$-face. For each two consecutive vertices $v_{i+1},v_{i+2}\in N_{4,5}^H\left(v\right)$, ${\displaystyle \sum _{j=1}^2}\tau (v\to v_{i+j})\le \frac{6-4-1}{4-1}+\frac{6-4-1}{4-1}=\frac{2}{3}$ by (R1) and Observation 1.

• $d_{6^{+}}^H\left(v\right)=3$. Then, $d_3^H\left(v\right)\le 1$, and there exist two consecutive vertices $v_{i+1},v_{i+2}\in N_{4,5}^H\left(v\right)$ such that ${\displaystyle \sum _{j=1}^2}\tau (v\to v_{i+j})\le \frac{2}{3}$. Hence, ${\omega }^{\prime }\left(v\right)\ge 5-1-\frac{2}{3}-\frac{2}{3}\times (11-1-2-3)=0$ by Observation 2.
• $d_{6^{+}}^H\left(v\right)=2$. Then, $d_3^H\left(v\right)=0$, and there are two vertex-disjoint subsets $\{v_{i+1},v_{i+2}\}$, $\{v_{m+1},v_{m+2}\}\subseteq N_{4,5}^H\left(v\right)$ such that ${\displaystyle \sum _{j=1}^2}\tau (v\to v_{i+j})\le \frac{2}{3}$ and ${\displaystyle \sum _{j=1}^2}\tau (v\to v_{m+j})\le \frac{2}{3}$. Hence, ${\omega }^{\prime }\left(v\right)\ge 5-1-\frac{2}{3}\times 2-\frac{2}{3}\times (11-1-2-2-2)=0$ by Observation 2.

Case 6.2.v is not in any special 3-face. By Claim 4(2), $d_2^H\left(v\right)\le 1$. Let $q=d_2^H\left(v\right)+d_{6^{+}}^H\left(v\right)$, $v_{i_1},v_{i_2},\dots ,v_{i_q}$ be $6^{+}$-vertices or 2-vertices with $0=i_1<i_2<\cdots <i_q$, and $n_j=|\left\{l|i_j+1\le l\le i_{j+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$ for $j\in [1,q]$. Then, $i_{q+1}-1=10$ and ${\displaystyle \sum _{j=1}^q}{n}_j=11-q$. By Observation 3, ${\displaystyle \sum _{l=i_j+1}^{i_{j+1}-1}}\tau (v\to v_l)\le \frac{n_j}{3}+1$ for $j\in [1,q]$. If $q\ge 6$, then ${\omega }^{\prime }\left(v\right)\ge 5-(11-q)=q-6\ge 0$ by Observation 2. If $q\le 1$, then ${\omega }^{\prime }\left(v\right)\ge 5-(\frac{11-q}{3}+1)=\frac{1}{3}q+\frac{1}{3}\ge \frac{1}{3}$ by Observation 3. Otherwise, $q\in [2,5]$.

• $d_2^H\left(v\right)=1$. By Claim 10(9), $q-1=d_{6^{+}}^H\left(v\right)\ge d_{3^{-}}^H\left(v\right)+1=d_3^H\left(v\right)+2$. Then $q\ge d_3^H\left(v\right)+3\ge 3$. If $q\in [4,5]$, then ${\omega }^{\prime }\left(v\right)\ge 5-(q-3)-\frac{2}{3}\times (11-q-q+3)=\frac{1}{3}q-\frac{4}{3}\ge 0$ by Observation 2. If $q=3$, then $d_3^H\left(v\right)=0$, and there are three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_{4,5}^H\left(v\right)$. By Observation 3(4), ${\displaystyle \sum _{j=1}^3}\tau (v\to v_{i+j})\le \frac{4}{3}$. Hence, ${\omega }^{\prime }\left(v\right)\ge 5-\frac{4}{3}-\frac{2}{3}\times (11-3-3)=\frac{1}{3}$ by Observation 2.
• $d_2^H\left(v\right)=0$. If v is adjacent to a $T_1^2$-3-vertex, by Claim 10(9), then $q=d_{6^{+}}^H\left(v\right)\ge d_3^H\left(v\right)+3\ge 4$, $d_3^H\left(v\right)\le q-3$ and ${\omega }^{\prime }\left(v\right)\ge 5-(q-3)-\frac{2}{3}\times (11-q-q+3)=\frac{1}{3}q-\frac{4}{3}\ge 0$ by Observation 2. Thus, we assume that v is not adjacent to any $T_1^2$-3-vertex. For each $v_i\in N_3^H\left(v\right)$ with $d_3^H\left(v_i\right)=1$, $\tau (v\to v_i)\le \frac{6-3-2}{3-1}=\frac{1}{2}$. For each s consecutive vertices $v_{i+1},v_{i+2},\dots ,v_{i+s}\in N_{3,4,5}^H\left(v\right)$, ${\displaystyle \sum _{j=1}^s}\tau (v\to v_{i+j})\le \frac{2}{3}+\frac{s-2}{3}+\frac{2}{3}=\frac{s}{3}+\frac{2}{3}$ by (R1) and Observation 1. If $q\le 4$, then ${\omega }^{\prime }\left(v\right)\ge 5-{\displaystyle \sum _{j=1}^q}(\frac{n_j}{3}+\frac{2}{3})=\frac{4}{3}-\frac{q}{3}\ge 0$.

Assume that $q=5$. If there exist three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_{3,4,5}^H\left(v\right)$, then ${\omega }^{\prime }\left(v\right)\ge 5-(\frac{3}{3}+\frac{2}{3})-(11-5-3)=\frac{1}{3}$ by Observation 2. If there exist $a,b\in [1,5]$ with $n_a=n_b=2$, then ${\omega }^{\prime }\left(v\right)\ge 5-(\frac{2}{3}+\frac{2}{3})\times 2-(11-5-2-2)=\frac{1}{3}$ by Observation 2. Otherwise, there are nine consecutive vertices $v_{i+1},v_{i+2},\dots ,v_{i+9}$ with $v_{i+2},v_{i+4},v_{i+6},v_{i+8}\in N_{3,4,5}^H\left(v\right)$ and $v_{i+1},v_{i+3},v_{i+5},v_{i+7},v_{i+9}\in N_{6^{+}}^H\left(v\right)$. If there are at most three 3-vertices in $\{v_{i+2},v_{i+4},v_{i+6},v_{i+8}\}$, then ${\omega }^{\prime }\left(v\right)\ge 5-(\frac{2}{3}+\frac{2}{3})-1\times 3-\frac{2}{3}=0$ by Observation 2. Thus, we assume that $v_{i+2},v_{i+4},v_{i+6},v_{i+8}\in N_3^H\left(v\right)$. By the nonexistence of $G_5$ in Claim 5(3), there are two subscripts $a,b\in \{i+2,i+4,i+6,i+8\}$ such that one of $f_{a-1}$ and $f_a$ is at least a 4-face without 2-vertex or $5^{+}$-face, and one of $f_{b-1}$ and $f_b$ is at least a 4-face without 2-vertex or $5^{+}$-face. Hence, ${\omega }^{\prime }\left(v\right)\ge 5-(\frac{2}{3}+\frac{2}{3})-\frac{6-3-1}{3}\times 2-1\times 2=\frac{1}{3}$ by Observation 2.

Case 7.$k=12$. Then, $\omega \left(v\right)=6$. If v is in $G_1$, by Claim 10(10), then $d_{6^{+}}^H\left(v\right)\ge 2$. Hence, by Observation 2, ${\omega }^{\prime }\left(v\right)\ge 6-\frac{3}{2}\times 2-\frac{1}{3}\times (12-2-d_{6^{+}}^H\left(v\right))=\frac{1}{3}{d}_{6^{+}}^H\left(v\right)-\frac{1}{3}\ge \frac{1}{3}$. Thus, we assume that v is not in $G_1$. If v is in a bad 3-face, by Claim 10(10), then $d_{6^{+}}^H\left(v\right)\ge 2$. Hence, ${\omega }^{\prime }\left(v\right)\ge 6-1\times 2-\frac{1}{2}\times (12-2-d_{6^{+}}^H\left(v\right))=\frac{1}{2}{d}_{6^{+}}^H\left(v\right)-1\ge 0$ by Observation 2. Thus, we assume that v is not in a bad 3-face.

Case 7.1.v is in a special 3-face. By Claim 4(4), $d_2^H\left(v\right)=1$. For each $v_i\in N_{3,4,5}^H\left(v\right)$, $\tau (v\to v_i)\le \frac{2}{3}$ by Observation 2. For each s consecutive vertices $v_{i+1},v_{i+2},\dots ,v_{i+s}\in N_{3,4,5}^H\left(v\right)$, ${\displaystyle \sum _{j=1}^s}\tau (v\to v_{i+j})\le \frac{2}{3}+\frac{s-2}{3}+\frac{2}{3}=\frac{s}{3}+\frac{2}{3}$ by (R1) and Observation 1.

Let $p=d_{6^{+}}^H\left(v\right)$, $v_{i_1},v_{i_2},\dots ,v_{i_p}$ be $6^{+}$-vertices, where $0=i_1<i_2<\cdots <i_p$ and $v_{i_p+1}$ is a 2-vertex. Let $n_j=|\left\{l|i_j+1\le l\le i_{j+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$ for $j\in [1,p-1]$, and $n_p=|\left\{l|i_p+2\le l\le i_{p+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$. Then, $i_{p+1}-1=11$, ${\displaystyle \sum _{j=1}^p}{n}_j=11-p$, ${\displaystyle \sum _{l=i_j+1}^{i_{j+1}-1}}\tau (v\to v_l)\le \frac{n_j}{3}+\frac{2}{3}$ for $j\in [1,p-1]$ and ${\displaystyle \sum _{l=i_p+2}^{i_{p+1}-1}}\tau (v\to v_l)\le \frac{n_p}{3}+\frac{2}{3}$. If $p\ge 6$, by Observation 2, then ${\omega }^{\prime }\left(v\right)\ge 6-1-(12-1-p)=p-6\ge 0$. If $p\le 4$, then ${\omega }^{\prime }\left(v\right)\ge 6-1-{\displaystyle \sum _{j=1}^p}(\frac{n_j}{3}+\frac{2}{3})=\frac{4}{3}-\frac{1}{3}p\ge 0.$ If $p=5$, then there exist two consecutive vertices $v_{i+1},v_{i+2}\in N_{3,4,5}^H\left(v\right)$. Hence, ${\omega }^{\prime }\left(v\right)\ge 6-1-(\frac{2}{3}+\frac{2}{3})-\frac{2}{3}\times (12-1-5-2)=1$ by Observation 2.

Case 7.2.v is not in any special 3-face. Let $q=d_2^H\left(v\right)+d_{6^{+}}^H\left(v\right)$, $v_{i_1},v_{i_2},\dots ,v_{i_q}$ be $6^{+}$-vertices or 2-vertices, where $0=i_1<i_2<\cdots <i_q$, and $n_j=|\left\{l|i_j+1\le l\le i_{j+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$ for $j\in [1,q]$. Then, $i_{q+1}-1=11$ and ${\displaystyle \sum _{j=1}^q}{n}_j=12-q$. By Observation 3, ${\displaystyle \sum _{l=i_j+1}^{i_{j+1}-1}}\tau (v\to v_l)\le \frac{n_j}{3}+1$ for $j\in [1,q]$. If $q\ge 6$, by Observation 2, then ${\omega }^{\prime }\left(v\right)\ge 6-(12-q)=q-6\ge 0$. If $q\le 3$, then ${\omega }^{\prime }\left(v\right)\ge 6-{\displaystyle \sum _{j=1}^q}(\frac{n_j}{3}+1)=2-\frac{2q}{3}\ge 0.$

• $q=5$. If there exist three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_{3,4,5}^H\left(v\right)$, by Observations 2 and 3, then ${\omega }^{\prime }\left(v\right)\ge 6-(\frac{3}{3}+1)-(12-5-3)=0$. Otherwise, there are $a,b\in [1,5]$ with $n_a=n_b=2$. By Observations 2 and 3, ${\omega }^{\prime }\left(v\right)\ge 6-2\times \frac{3}{2}-(12-5-2-2)=0$.
• $q=4$. If there exist five consecutive vertices $v_{i+1},v_{i+2},\dots ,v_{i+5}\in N_{3,4,5}^H\left(v\right)$, by Observations 2 and 3, then ${\omega }^{\prime }\left(v\right)\ge 6-(\frac{5}{3}+1)-(12-4-5)=\frac{1}{3}$. If there exist $a,b\in [1,4]$ with $n_a=4$ and $n_b=2$, by Observations 2 and 3, then ${\omega }^{\prime }\left(v\right)\ge 6-(\frac{4}{3}+1)-\frac{3}{2}-(12-4-4-2)=\frac{1}{6}$. If there exist $a,b\in [1,4]$ with $n_a=n_b=3$, by Observations 2 and 3, then ${\omega }^{\prime }\left(v\right)\ge 6-(\frac{3}{3}+1)\times 2-(12-4-3-3)=0$. If there exist $s,t,r\in [1,4]$ with $n_s=3$ and $n_t=n_r=2$, then ${\omega }^{\prime }\left(v\right)\ge 6-(\frac{3}{3}+1)-\frac{3}{2}\times 2-(12-4-3-2-2)=0$ by Observations 2 and 3. Otherwise, $n_1=n_2=n_3=n_4=2$. By Observation 3, ${\omega }^{\prime }\left(v\right)\ge 6-4\times \frac{3}{2}=0$.

Case 8.$k=13$. Then, $\omega \left(v\right)=7$. If v is in $G_1$, by Observation 2, then ${\omega }^{\prime }\left(v\right)\ge 7-2\times \frac{3}{2}-\frac{1}{3}\times (13-2-d_{6^{+}}^H\left(v\right))\ge \frac{1}{3}{d}_{6^{+}}^H\left(v\right)+\frac{1}{3}\ge \frac{1}{3}$. Thus, we assume that v is not in $G_1$.

Assume that v is in a bad 3-face. Then, $d_2^H\left(v\right)=0$ and v is in at most one bad 3-face by Claim 5(1). If $d_{6^{+}}^H\left(v\right)\ge 1$, then ${\omega }^{\prime }\left(v\right)\ge 7-1\times 2-\frac{1}{2}\times (13-2-d_{6^{+}}^H\left(v\right))=\frac{1}{2}{d}_{6^{+}}^H\left(v\right)-\frac{1}{2}\ge 0$ by Observation 2. Otherwise, $d_{6^{+}}^H\left(v\right)=0$. Suppose that $d_H\left(v_j\right)=s\in [3,5]$ for $j\in [2,12]$. If $d_s^H\left(v_j\right)=0$, then $f_{j-1}$ and $f_j$ are 4-faces without 2-vertices or $5^{+}$-faces. Hence, by (R1) and Observation 1, $\tau (v\to v_j)\le \frac{6-s-2}{s}\le \frac{1}{3}$. If $d_s^H\left(v_j\right)=1$ and $s\ge 4$, then $d_{5^{-}}^H\left(v_j\right)=d_s^H\left(v_j\right)=1$ by Claim 10(3). Then, we can conclude that at least one of $f_{j-1}$ and $f_j$ is a $4^{+}$-face. Hence, by (R1) and Observation 1, $\tau (v\to v_j)\le \frac{6-s-1}{s-1}\le \frac{1}{3}$. If $s=3$ and $d_3^H\left(v_j\right)=1$, then one of $f_{j-1}$ and $f_j$ is a 4-face without 2-vertex or $5^{+}$-face, and the other is a $5^{+}$-face. Hence, by (R1) and Observation 1, $\tau (v\to v_j)\le \frac{6-3-1-\frac{4}{3}}{3-1}=\frac{1}{3}$. Therefore, we have ${\displaystyle \sum _{j=2}^{12}}\tau (v\to v_j)\le \frac{11}{3}$, and ${\omega }^{\prime }\left(v\right)\ge 7-1\times 2-\frac{11}{3}=\frac{4}{3}$. Thus, we assume that v is not in a bad 3-face.

Case 8.1.v is in a special 3-face. By Claim 4(4), $d_2^H\left(v\right)=1$. For each $v_i\in N_{3,4,5}^H\left(v\right)$, $\tau (v\to v_i)\le \frac{2}{3}$ by Observation 2. For each s consecutive vertices $v_{i+1},v_{i+2},\dots ,v_{i+s}\in N_{3,4,5}^H\left(v\right)$, ${\displaystyle \sum _{j=1}^s}\tau (v\to v_{i+j})\le \frac{2}{3}+\frac{s-2}{3}+\frac{2}{3}=\frac{s}{3}+\frac{2}{3}$ by (R1) and Observation 1.

Let $p=d_{6^{+}}^H\left(v\right)$, $v_{i_1},v_{i_2},\dots ,v_{i_p}$ be $6^{+}$-vertices, where $0=i_1<i_2<\cdots <i_p$ and $v_{i_p+1}$ is a 2-vertex. Let $n_j=|\left\{l|i_j+1\le l\le i_{j+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$ for $j\in [1,p-1]$ and $n_p=|\left\{l|i_p+2\le l\le i_{p+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$. Then, $i_{p+1}-1=12$, ${\displaystyle \sum _{j=1}^p}{n}_j=12-p$, ${\displaystyle \sum _{l=i_j+1}^{i_{j+1}-1}}\tau (v\to v_l)\le \frac{n_j}{3}+\frac{2}{3}$ for $j\in [1,p-1]$ and ${\displaystyle \sum _{l=i_p+2}^{i_{p+1}-1}}\tau (v\to v_l)\le \frac{n_p}{3}+\frac{2}{3}$. If $p\ge 6$, by Observation 2, then ${\omega }^{\prime }\left(v\right)\ge 7-1-(13-1-p)=p-6\ge 0$. If $p\le 5$, then ${\omega }^{\prime }\left(v\right)\ge 7-1-{\displaystyle \sum _{j=1}^p}(\frac{n_j}{3}+\frac{2}{3})=2-\frac{1}{3}p\ge \frac{1}{3}$ by Observation 2.

Case 8.2.v is not in any special 3-face. Let $q=d_2^H\left(v\right)+d_{6^{+}}^H\left(v\right)$, $v_{i_1},v_{i_2},\dots ,v_{i_q}$ be $6^{+}$-vertices or 2-vertices, where $0=i_1<i_2<\cdots <i_q$, and $n_j=|\left\{l|i_j+1\le l\le i_{j+1}-1,3\le d_H\left(v_l\right)\le 5\}\right|$ for $j\in [1,q]$. Then, $i_{q+1}-1=12$ and ${\displaystyle \sum _{j=1}^q}{n}_j=13-q$. By Observations 2 and 3, ${\displaystyle \sum _{l=i_j+1}^{i_{j+1}-1}}\tau (v\to v_l)\le \frac{n_j}{3}+1$ for $j\in [1,q]$. If $q\ge 6$, by Observation 2, then ${\omega }^{\prime }\left(v\right)\ge 7-(13-q)=q-6\ge 0$. If $q\le 4$, then ${\omega }^{\prime }\left(v\right)\ge 7-{\displaystyle \sum _{j=1}^q}(\frac{n_j}{3}+1)=\frac{8}{3}-\frac{2q}{3}\ge 0$.

Assume that $q=5$. If there exist three consecutive vertices $v_{i+1},v_{i+2},v_{i+3}\in N_{3,4,5}^H\left(v\right)$, by Observations 2 and 3, then ${\omega }^{\prime }\left(v\right)\ge 7-(\frac{3}{3}+1)-(13-5-3)=0$. Otherwise, there exist $a,b\in [1,5]$ with $n_a=n_b=2$. By Observations 2 and 3, we have ${\omega }^{\prime }\left(v\right)\ge 7-\frac{3}{2}\times 2-(13-5-2-2)=0$.

4. Conclusions and Future Works

In this paper, we have accomplished the characterization for the neighbor-distinguishing index of planar graphs with $\Delta \ge 13$. In other words, we have proved that if G is a planar graph with $\Delta \ge 13$, then $\Delta \le {\chi }_a^{\prime }\left(G\right)\le \Delta +1$, and, further, that ${\chi }_a^{\prime }\left(G\right)=\Delta +1$ if and only if G contains two adjacent $\Delta$-vertices. This improves upon the results in [11,13]. We think that the condition that $\Delta \ge 13$ in Theorem 1 is not the best possible. Therefore, we propose the following problem.

Problem 1. 

Find the smallest positive integer $C(\le 12)$ such that if G is a planar graph $\Delta \ge C$, then $\Delta \le {\chi }_a^{\prime }\left(G\right)\le \Delta +1$, and further ${\chi }_a^{\prime }\left(G\right)=\Delta +1$ if and only if G contains two adjacent Δ-vertices.

So far, we have learned from the published papers that Conjecture 1 is true for planar graphs with $\Delta \ge 11$. Then, we propose the second problem below.

Problem 2. 

Prove that all plane graphs with $4\le \Delta \le 10$ satisfy Conjecture 1. If not, counterexamples can be found.