The adjacent vertex distinguishing total chromatic numbers of planar graphs with $\Delta =10$

Abstract

A (proper) total-k-coloring of a graph G is a mapping $\phi : V (G) \cup E(G)\mapsto \{1, 2, \ldots , k\}$ such that any two adjacent elements in $V (G) \cup E(G)$ receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total-k-adjacent vertex distinguishing-coloring of G is a total-k-coloring of G such that for each edge $uv\in E(G)$, $C(u)\ne C(v)$. We denote the smallest value k in such a coloring of G by $\chi ''_{a}(G)$. It is known that $\chi _{a}''(G)\le \Delta (G)+3$ for any planar graph with $\Delta (G)\ge 11$. In this paper, we show that if G is a planar graph with $\Delta (G)\ge 10$, then $\chi _{a}''(G)\le \Delta (G)+3$. Our approach is based on Combinatorial Nullstellensatz and the discharging method.

1 Introduction

Let G be a simple, undirected graph. Denote the vertex set, edge set, maximum degree and minimum degree of G by V(G), E(G), $\Delta (G)$ and $\delta (G)$ (or simply $V,E,\Delta$ and $\delta$), respectively. The terminology and notation used but undefined in this paper can be found in Bondy and Murty (1976).

A (proper) total-k-coloring of a graph G is a coloring of $V\cup {E}$ using k colors such that no two adjacent or incident elements receive the same color. A graph G is total- k -colorable if it admits a total-k-coloring. The total chromatic number $\chi ''(G)$ of G is the smallest integer k such that G is total-k-colorable.

Given a total- k -coloring $\phi$ of G, let $C_\phi (v)$ denote the set of the color of v and the colors of the edges incident with v. If $C_\phi (u)$ is different from $C_\phi (v)$ for each edge uv, then this total-k-coloring is called adjacent vertex distinguishing, or total- k -avd-coloring for short. The smallest k is called the adjacent vertex distinguishing total chromatic number, denoted by $\chi ''_{a}(G)$.

Let $\chi (G)$ and $\chi '(G)$ denote the vertex chromatic number and the edge chromatic number of G respectively. Then we have the following relation:

Proposition 1

For any graph G, $\chi ''_{a}(G)\le \chi (G)+\chi '(G)$.

Suppose that G is a planar graph. Then $\chi (G)\le 4$ by the Four-Color Theorem (Appel and Haken 1977; Appel et al. 1977) and $\Delta (G)\le \chi '(G)\le \Delta (G)+1$ by Vizing (1964). So $\chi ''_{a}(G)\le \Delta (G)+5$. Particularly, since $\chi '(G)= \Delta (G)$ when $\Delta (G)\ge 7$ by Sanders and Zhao (2001), $\chi ''_{a}(G)\le \Delta (G)+4$. Zhang et al. proposed the following conjecture in Zhang et al. (2005):

Conjecture 1

(Zhang et al. 2005) For any graph G with at least two vertices, $\chi ''_{a}(G)\le \Delta (G)+3$.

Coker and Johannson (2012) used a probabilistic method to establish an upper bound $\Delta (G) + c$ for $\chi ''_{a}(G)$, where $c > 0$ is a constant. Later, Huang et al. (2012) proved that $\chi ''_{a}(G)\le 2\Delta (G)$ for any graph G with maximum degree $\Delta (G) \ge 3$. Conjecture 1 was confirmed for graphs with maximum degree at most three by Chen (2008) and independently by Wang (2007). Wang and Wang proved that this conjecture holds for outerplanar graphs (Wang and Wang 2010) and $K_4$-minor free graphs (Wang and Wang 2009). Huang and Wang proved that $\chi ''_{a}(G)\le \Delta (G)+2$ for planar graphs with maximum degree at least 14 in Wang and Huang (2014), and they also proved the following result:

Theorem 1

(Huang and Wang 2012) Let G be a planar graph with maximum degree $\Delta (G)\ge 11$. Then $\chi _{a}''(G)\le \Delta (G)+3$.

In this paper, we prove the following result, which improves the bound in Huang and Wang (2012).

Theorem 2

Let G be a planar graph with maximum degree $\Delta (G)\ge 10$. Then $\chi _{a}''(G)\le \Delta (G)+3$.

Recently the adjacent vertex distinguishing total coloring by sums has been considered. For a total-k-coloring $\phi$ of G, let $m_{\phi }(v)$ denote the total sum of colors of the edges incident with v and the color of v. If $m_{\phi }(u)\ne m_{\phi }(v)$ for each edge uv, then this total-k-coloring is called a total-k-neighbor sum distinguishing-coloring. The smallest number k is called the neighbor sum distinguishing total chromatic number. For this coloring, see Cheng et al. (2015), Ding et al. (2014), Dong and Wang (2014), Li et al. (2015), Li et al. (2013), Pilśniak and Woźniak (2015).

2 Notations and preliminaries

For a given planar graph G, a vertex of degree k (at least k, at most k) is called a k-vertex ($k^+$-vertex, $k^-$-vertex). A face of degree k (at least k, at most k) is called a k-face ($k^+$-face, $k^-$-face). Denote the set of faces of G by F(G). For $x \in V (G) \cup F(G)$, let $d_G (x)$ denote the degree of x in G. For a vertex $v\in V(G)$, we use $N^G_k(v)$ to denote the set of k-vertices adjacent to v in G, and let $n^G_k(v) = |N^G_k(v)|$. Similarly, we define $n^G_{k^+}(v)$ and $n^G_{k^-}(v)$. If there is no confusion in the context, we usually write $n^G_k (x)$, $n^G_{k^+}(x)$ and $n^G_{k^-}(x)$ as $n_k (x$), $n_{k^+}(x)$ and $n_{k^-}(x)$ respectively.

Suppose that $\phi$ is a total-k-avd-coloring of a planar graph G and $v\in V$. Recall $C_{\phi }(v)$ is the set of the color of v and the colors of the edges incident with v and $m_{\phi }(v)$ is the total sum of colors in $C_\phi (v)$. Obviously, for two adjacent vertices u and v, if $m_{\phi }(u)\ne m_{\phi }(v)$, then $C_\phi (u)\ne C_\phi (v)$. We call two adjacent vertices u and v conflict on $\phi$ if $C_ {\phi }(u)=C_{\phi }(v)$. Let $D_{\phi }(v)$ denote the union of $C_{\phi }(v)$ and the colors of vertices adjacent to v. Now we state the Combinatorial Nullstellensatz.

Lemma 1

(Alon (1999), Combinatorial Nullstellensatz) Let ${\mathbb {F}}$ be an arbitrary field, and let $P = P(x_1, \ldots , x_n)$ be a polynomial in ${\mathbb {F}}[x_1, \ldots , x_n]$. Suppose the degree deg(P) of P equals $\sum ^n_{i=1}k_i$, where each $k_i$ is a non-negative integer, and suppose the coefficient of $x_1^{k_1}\cdots x_n^{k_n}$ in P is non-zero. Then if $S_1,\ldots , S_n$ are subsets of ${\mathbb {F}}$ with $|S_i| > k_i, i=1,\ldots ,n$, there exist $s_1\in S_1,\ldots , s_n\in S_n$ so that $P(s_1, \ldots , s_n)\ne 0$.

3 Proof of the main theorem

From Theorem 1 we know that if G is a planar graph with $\Delta (G)\ge 11$, then $\chi _a''(G)\le \Delta +3$, so we only need to consider $\Delta (G)=10$. Let G be a counterexample of Theorem 2 such that $|V(G)|+|E(G)|$ is as small as possible. Obviously, G is connected.

Let e be any edge of G and $H=G-e$. If $\Delta (H)=\Delta (G)=10$, then by the minimality of G, $\chi _a''(H)\le 13$. If $\Delta (H)=\Delta (G)-1=9$, then by Proposition 1, $\chi _a''(H)\le \Delta (H)+4=13$. Therefore, $\chi _a''(H)\le 13$ for both cases.

Note that if $P(x_1,x_2,\ldots ,x_m)$ is a polynomial with $\deg (P)=n$, $k_1,k_2,\ldots ,k_m$ are non-negative integers with $\sum \limits _{i=1}^{m} k_i=n$ and $c_P(x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m})$ is the coefficient of monomial $x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$ in P, then $\frac{\partial ^n P}{\partial x_1^{k_1}\partial x_2^{k_2}\cdots \partial x_m^{k_m}}=c_P(x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m})\prod _{i=1}^{m}k_i!$. In the following, we always use MATLAB to calculate the coefficients of specific monomials. The codes are listed in Appendix.

3.1 Unavoidable configurations

Claim 1

There is no edge $uv \in E(G)$ such that $d(v) \le 6$ and $d(u) \le 5$.

Proof

Assume to the contrary that G contains an edge uv such that $d(v)=t\le 6$ and $d(u)=s\le 5$, and $s\le t$. Let $H=G-uv$. Then there exists a total-13-avd-coloring $\psi$ of H by the above analysis. Without loss of generality, we assume that $C=\{1,2,\ldots ,13\}$ is the set of all colors used in $\psi$. Let $u_1,u_2,\ldots ,u_{s-1}$ be the neighbors of u other than v, and $v_1,v_2,\ldots ,v_{t-1}$ be the neighbors of v other than u.

Case 1 $t\le 5$. Without loss of generality, we may assume that $s=t=5$ (We can get an easier proof for other cases). Erase the colors of u, v and denote this partial total-13-avd-coloring by $\phi '$. Let $S_{1}=C\setminus D_{\phi '}(u)$, $S_{2}=C\setminus (C_{\phi '}(u)\cup C_{\phi '}(v))$ and $S_{3}=C\setminus D_{\phi '}(v)$. Then $|S_i|\ge 5$ for $i=1,2,3$. Now we extend $\phi '$ to G. We will color u, uv, v with the colors $s_i\in S_{i}, i=1,2,3$ respectively (see Fig. 1(1)). Let $\phi$ denote the coloring after u, uv, v are colored. If $s_i-s_j\ne 0$ for $1\le i<j\le 3$, then $\phi$ is a proper total coloring. If $m_{\phi }(u)\ne m_{\phi }(u_i)$, $m_{\phi }(v)\ne m_{\phi }(v_i)$ for $i=1,2,3,4$, and $m_{\phi }(u)\ne m_{\phi }(v)$, then $\phi$ is an adjacent vertex distinguishing coloring. Hence $\phi$ would be a total-13-avd-coloring if there exist $s_i\in S_i,i=1,2,3$ such that $P(s_1,s_2,s_3)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,x_3)=&\,(x_1-x_2)(x_1-x_3)(x_2-x_3) (x_1+m_{\phi '}(u)-(x_3+m_{\phi '}(v)))\\&\prod _{i=1}^4(x_1+x_2+m_{\phi '}(u)-m_{\phi '}(u_{i}))\prod _{i=1}^4(x_3+x_2+m_{\phi '}(v)-m_{\phi '}(v_{i})). \end{aligned}$$

Fig. 1

Configurations in the proof of Claim 1

By MATLAB, we obtain that $c_P(x_1^{4}x_2^{4}x_3^{4})=c_Q(x_1^{4}x_2^{4}x_3^{4})=20\ne 0$, where $Q(x_1,x_2,x_3)=(x_1-x_2)(x_1-x_3)^2(x_2-x_3)(x_1+x_2)^4(x_2+x_3)^4$. According to Lemma 1, since $\deg (P)=12$ and $|S_i|\ge 5,i=1,2,3$, there exist $s_i\in S_i, i=1,2,3$ such that $P(s_1,s_2,s_3)\ne 0$. Coloring u, uv, v with $s_1,s_2,s_3$ respectively and then we obtain a total-13-avd-coloring of G, which is a contradiction.

Case 2 $t=6$. Without loss of generality, we may assume that $s=5$ and $t=6$ (We can get an easier proof for other cases). Erase the color of u. We conclude that $d(u_i)\ne d(u)$ for any $i\in \{1,2,3,4\}$ by Case 1. Suppose that $\psi (v)=1,\psi (vv_i)=i+1$ for $i\in \{1,2,\ldots ,5\}$, and $\psi (uu_j)=a_{j}$ for $j\in \{1,2,3,4\}$. Without loss of generality, assume $\{a_1,a_2,a_3,a_4\}\subseteq \{1,2,\ldots ,10\}$ (see Fig. 1(2)). If there exists a color $x\in \{11,12,13\}$ such that coloring uv with x cannot result in conflicting vertices, then we color uv with the color x. Otherwise, without loss of generality, we can assume the conflicting vertices are $v_1,v_2,v_3$ respectively, which means that $C_{\psi }(v_i)=\{1,2,\ldots ,6,i+10\}$ for $i=1,2,3$. Recolor v with a color $a\in \{7,8,9,10\}\backslash \{\psi (v_4),\psi (v_5)\}$. Since now the possible conflicting vertices of v are $v_4$ and $v_5$, we can choose a color in $\{11,12,13\}$ to color uv such that v does not conflict with $v_4$ and $v_5$. Finally, we color u. Since $d(u_i)\ne d(u), i=1,2,3,4$, u have at most 10 forbidden colors. Thus we can color u safely and then we obtain a total-13-avd-coloring of G, which is a contradiction. $\square$

Suppose $\phi$ is a partial total-13-avd-coloring of G. We call $\phi$ to be a nice total-13-avd-coloring of G if only some $5^-$-vertices are not colored. Observe that every nice total-13-avd-coloring can be greedily extended to a total-13-avd-coloring of G since each $5^-$-vertex v has at most 10 forbidden colors by Claim 1.

Claim 2

If v is a 7-vertex of G, then $n_{5^-}(v)\le 2$. Moreover, if $n_{3^-}(v)\ge 1$, then $n_{5^-}(v)=1$.

Proof

Let $v_1, v_2, \ldots , v_7$ be the neighbors of v with $d(v_1)\le d(v_2)\le \cdots \le d(v_7)$.

(1) Suppose to the contrary that $n_{5^-}(v)\ge 3$. Then $d(v_1)\le d(v_2)\le d(v_3)\le 5$. Let $H=G-vv_1-vv_2-vv_3$. Thus there exists a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v, v_1,v_2,v_3$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$. Let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,3$, and let $S_{4}=C\setminus D_{\phi '}(v)$. Then $|S_{i}|\ge 5$ for $i=1,2,3,4$. We will color $vv_i$ with the color $s_i\in S_{i}$ for $i = 1,2,3$ and color v with the color $s_4\in S_4$. Let $\phi$ denote the partial coloring after $vv_1,vv_2,vv_3$ and v are colored. If $s_i-s_j\ne 0$ for $1\le i< j\le 4$, then $\phi$ is a proper total coloring. If $m_{\phi }(v)\ne m_{\phi }(v_i)$, i.e., $\sum _{t=1}^4 s_t+m_{\phi '}(v)-m_{\phi '}(v_i)\ne 0$ for $i=4,5,6,7$, then $\phi$ is an adjacent vertex distinguishing coloring. Hence $\phi$ would be a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,3,4$ such that $P(s_1,s_2,s_3,s_4)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,x_3,x_4)=\prod _{1\le i<j\le 4}(x_i-x_j)\prod _{i=4}^7\left( \sum _{t=1}^4 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

By MATLAB, $c_P(x_1^{4}x_2^{3}x_3^{2}x_4)=c_Q(x_1^{4}x_2^{3}x_3^{2}x_4)=1\ne 0$, where $Q(x_1,x_2,x_3,x_4)=\prod _{1\le i<j\le 4}(x_i-x_j)(\sum _{t=1}^4 x_t)^4$. According to Lemma 1, since $\deg (P)=10$ and $|S_i|\ge 5$ for $i=1,2,3,4$, there exist $s_i\in S_i, i=1,2,3,4$ such that $P(s_1,s_2,s_3,s_4)\ne 0$. Coloring $vv_1,vv_2,vv_3,v$ with $s_1,s_2,s_3,s_4$ respectively and then we obtain a nice total-13-avd-coloring, which is a contradiction.

(2) Suppose $n_{5^-}(v)\ge 2$ when $n_{3^-}(v)\ge 1$. Then $d(v_1)\le 3$ and $d(v_2)\le 5$. Let $H=G-vv_1-vv_2$. Then there exists a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v_1,v_2$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$ and let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2$. Obviously, $|S_{1}|\ge 5$ and $|S_{2}|\ge 3$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1$ and $vv_2$ are colored. Let $s_1,s_2$ correspond to the colors of $vv_1,vv_2$ respectively. Similar to (1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2$ such that $P(s_1,s_2)\ne 0$, where

$$\begin{aligned} P(x_1,x_2)=(x_1-x_2)\prod _{3\le i\le 7}(x_1+x_2+m_{\phi '}(v)-m_{\phi '}(v_i)). \end{aligned}$$

By MATLAB, $c_P(x_1^{4}x_2^{2})=c_Q(x_1^{4}x_2^{2})=5$, where $Q(x_1,x_2)=(x_1-x_2)(x_1+x_2)^5$. According to Lemma 1, since $\deg (P)=6$, $|S_{1}|\ge 5$ and $|S_{2}|\ge 3$, there exist $s_i\in S_i, i=1,2$ such that $P(s_1,s_2)\ne 0$. Coloring $vv_1,vv_2$ with $s_1,s_2$ respectively and then we obtain a nice total-13-avd-coloring, which is a contradiction. $\square$

Claim 3

Suppose v is an 8-vertex of G. If $n_{4^-}(v)\ge 1$, then $n_{5^-}(v)\le 3$. Moreover, if $n_{3^-}(v)\ge 2$, then $n_{5^-}(v)=2$.

Proof

Let $v_1, v_2, \ldots , v_8$ be the neighbors of v with $d(v_1)\le d(v_2)\le \cdots \le d(v_8)$.

(1) Suppose to the contrary that $n_{5^-}(v)\ge 4$ when $n_{4^-}(v)\ge 1$. Then $d(v_1)\le 4$ and $d(v_2)\le d(v_3)\le d(v_4)\le 5$. Let $H=G-vv_1-vv_2-vv_3-vv_4$. Then there exists a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,v_3$ and $v_4$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$ and let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,3,4$. Obviously, $|S_{1}|\ge 5$ and $|S_{i}|\ge 4$ for $i=2,3,4$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1,vv_2,vv_3$ and $vv_4$ are colored. Let $s_1,s_2,s_3,s_4$ correspond to the colors of $vv_1,vv_2,vv_3,vv_4$ respectively. Similar to Claim 2(1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,3,4$ such that $P(s_1,s_2,s_3,s_4)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,x_3,x_4)=\prod _{1\le i<j\le 4}(x_i-x_j)\prod _{5\le i\le 8}\left( \sum _{t=1}^4 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

By MATLAB, $c_P(x_1^{4}x_2^{3}x_3^{2}x_4)=c_Q(x_1^{4}x_2^{3}x_3^{2}x_4)=1$, where $Q(x_1,x_2,x_3,x_4)=\prod _{1\le i<j\le 4}(x_i-x_j)(\sum _{t=1}^4 x_t)^4$. According to Lemma 1, since $\deg (P)=10$, $|S_{1}|\ge 5$ and $|S_{i}|\ge 4$ for $i=2,3,4$, there exist $s_i\in S_{i},i=1,2,3,4$ such that $P(s_1,s_2,s_3,s_4)\ne 0$. Coloring $vv_1,vv_2,vv_3,vv_4$ with $s_1,s_2,s_3,s_4$ respectively and then we obtain a nice total-13-avd-coloring, which is a contradiction.

(2) Suppose to the contrary that $n_{5^-}(v)\ge 3$ when $n_{3^-}(v)\ge 2$. Then $d(v_1)\le d(v_2)\le 3$ and $d(v_3)\le 5$. Let $H=G-vv_1-vv_2-vv_3$. Then there exists a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v_1,v_2$ and $v_3$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$ and let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,3$. Then $|S_{1}|\ge 5$, $|S_{2}|\ge 5$ and $|S_{3}|\ge 3$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1,vv_2$ and $vv_3$ are colored. Let $s_1,s_2,s_3$ correspond to the colors of $vv_1,vv_2,vv_3$ respectively. Similar to Claim 2(1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,3$ such that $P(s_1,s_2,s_3)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,x_3)=\prod _{1\le i<j\le 3}(x_i-x_j)\prod _{4\le i\le 8}\left( \sum _{t=1}^3 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

By MATLAB, $c_P(x_1^{4}x_2^{3}x_3)=c_Q(x_1^{4}x_2^{3}x_3)=5$, where $Q(x_1,x_2,x_3)=\prod _{1\le i<j\le 3}(x_i-x_j)(\sum _{t=1}^3 x_t)^5$. According to Lemma 1, since $\deg (P)=8$, $|S_{1}|\ge 5$, $|S_{2}|\ge 5$ and $|S_{3}|\ge 3$, there exist $s_i\in S_{i},i=1,2,3$ such that $P(s_1,s_2,s_3)\ne 0$. Coloring $vv_1,vv_2,vv_3$ with $s_1,s_2,s_3$ respectively and then we obtain a nice total-13-avd-coloring, a contradiction. $\square$

Claim 4

Suppose v is a 9-vertex of G. If $n_{4^-}(v)\ge 1$ then $n_{5^-}(v)\le 6$. Moreover, if $n_{3^-}(v)\ge 1$ and $n_{4^-}(v)\ge 2$, then $n_{5^-}(v)\le 3$.

Proof

Let $v_1, v_2, \ldots , v_9$ be the neighbors of v with $d(v_1)\le d(v_2)\le \cdots \le d(v_9)$.

(1) Suppose to the contrary that $n_{5^-}(v)\ge 7$ when $n_{4^-}(v)\ge 1$. Then $d(v_1)\le 4$ and $d(v_2)\le d(v_3)\le \cdots \le d(v_7)\le 5$. Let $H=G-vv_1-vv_2-\cdots -vv_7$. Thus there is a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v,v_1,v_2,\ldots ,v_7$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$. Let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,\ldots ,7$ and let $S_{8}=C\setminus D_{\phi '}(v)$. Then $|S_{1}|\ge 8$, $|S_{i}|\ge 7$ for $i=2,3,\ldots ,7$ and $|S_{8}|\ge 9$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1,vv_2,\ldots ,vv_7$ and v are colored. Let $s_1,s_2,\ldots ,s_7$ and $s_8$ correspond to the colors of $vv_1,vv_2,\ldots ,vv_7$ and v respectively. Similar to Claim 2(1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,\ldots ,8$ such that $P(s_1,s_2,\ldots ,s_8)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,\ldots ,x_8)=\prod _{1\le i<j\le 8}(x_i-x_j)\prod _{8\le i\le 9}\left( \sum _{t=1}^8 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

By MATLAB, $c_P(x_1^{7}x_2^{5}x_3^{4}x_4^{3}x_5^2x_6x_8^8)=c_Q(x_1^{7}x_2^{5}x_3^{4}x_4^{3}x_5^2x_6x_8^8)=-1$, where $Q(x_1,x_2,\ldots ,x_8)= \prod _{1\le i<j\le 8} (x_i-x_j)(\sum _{t=1}^8 x_t)^2$. According to Lemma 1, since $\deg (P)=30$, $|S_{1}|\ge 8$, $|S_{i}|\ge 7$ for $i=2,3,\ldots ,7$ and $|S_{8}|\ge 9$, there exist $s_i\in S_{i},i=1,2,\ldots ,8$ such that $P(s_1,s_2,\ldots ,s_8)\ne 0$. Coloring $vv_1,vv_2\ldots ,vv_7$ and v with $s_1,s_2,\ldots ,s_7$ and $s_8$ respectively and then we obtain a nice total-13-avd-coloring, a contradiction.

(2) Suppose to the contrary that $n_{5^-}(v)\ge 4$ when $n_{3^-}(v)\ge 1$ and $n_{4^-}(v)\ge 2$. Then $d(v_1)\le 3$, $d(v_2)\le 4$ and $d(v_3)\le d(v_4)\le 5$. Let $H=G-vv_1-vv_2-vv_3-vv_4$. Thus there is a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v,v_1,v_2,v_3,v_4$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$. Let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,3,4$ and let $S_{5}=C\setminus D_{\phi '}(v)$. Then $|S_{1}|\ge 6$, $|S_{2}|\ge 5$, $|S_{3}|\ge 4$, $|S_{4}|\ge 4$ and $|S_{5}|\ge 3$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1,vv_2,vv_3,vv_4$ and v are colored. Let $s_1,s_2,s_3,s_4$ and $s_5$ correspond to the colors of $vv_1,vv_2,vv_3,vv_4$ and v respectively. Similar to Claim 2(1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,\ldots ,5$ such that $P(s_1,s_2,\ldots ,s_5)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,\ldots ,x_5)=\prod _{1\le i<j\le 5}(x_i-x_j)\prod _{5\le i\le 9}\left( \sum _{t=1}^5 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

By MATLAB, $c_P(x_1^{5}x_2^{4}x_3^{3}x_4^{2}x_5)=c_Q(x_1^{5}x_2^{4}x_3^{3}x_4^{2}x_5)=1$, where $Q(x_1,x_2,\ldots ,x_5)=\prod _{1\le i<j\le 5}(x_i-x_j)(\sum _{t=1}^5 x_t)^5$. According to Lemma 1, since $\deg (P)=15$, $|S_{1}|\ge 6$, $|S_{2}|\ge 5$, $|S_{3}|\ge 4$, $|S_{4}|\ge 4$ and $|S_{5}|\ge 3$, there exist $s_i\in S_{i},i=1,2,\ldots ,5$ such that $P(s_1,s_2,\ldots ,s_5)\ne 0$. Thus we obtain a nice total-13-avd-coloring, a contradiction.

$\square$

Claim 5

Suppose v is a 10-vertex of G and $n_{2^-}(v)\ge 1$. Then $n_{5^-}(v)\le 7$. Moreover, if $n_{3^-}(v)\ge 2$ and $n_{4^-}(v)\ge 3$, then $n_{5^-}(v)\le 4$.

Proof

Let $v_1, v_2, \ldots , v_{10}$ be the neighbors of v with $d(v_1)\le d(v_2)\le \cdots \le d(v_{10})$.

(1) Suppose to the contrary that $n_{5^-}(v)\ge 8$ when $n_{2^-}(v)\ge 1$. Then $d(v_1)\le 2$ and $d(v_2)\le d(v_3)\le \cdots \le d(v_8)\le 5$. Let $H=G-vv_1-vv_2-\cdots -vv_8$. Thus there is a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v,v_1,v_2,\ldots ,v_8$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$. Let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,\ldots ,8$ and let $S_{9}=C\setminus D_{\phi '}(v)$. Then $|S_{1}|\ge 10$, $|S_{i}|\ge 7$ for $i=2,3,\ldots ,8$ and $|S_{9}|\ge 9$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1,vv_2,\ldots ,vv_8$ and v are colored. Let $s_1,s_2,\ldots ,s_8$ and $s_9$ correspond to the colors of $vv_1,vv_2,\ldots ,vv_8$ and v respectively. Similar to Claim 2(1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,\ldots ,9$ such that $P(s_1,s_2,\ldots ,s_9)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,\ldots ,x_9)=\prod _{1\le i<j\le 9}(x_i-x_j)\prod _{9\le i\le 10}\left( \sum _{t=1}^9 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

Since $c_P(x_1^{9}x_2^{6}x_3^{5}x_4^{4}x_5^3x_6^2x_7x_9^8)=c_Q(x_1^{9}x_2^{6}x_3^{5}x_4^{4}x_5^3x_6^2x_7x_9^8)=-1$, where $Q(x_1,x_2,\ldots ,x_9)=\prod _{1\le i<j\le 9}(x_i-x_j)(\sum _{t=1}^9 x_t)^2$. According to Lemma 1, since $\deg (P)=38$, $|S_{1}|\ge 10$, $|S_{i}|\ge 7$ for $i=2,3,\ldots ,8$ and $|S_{9}|\ge 9$, there exist $s_i\in S_{i},i=1,2,\ldots ,9$ such that $P(s_1,s_2,\ldots ,s_9)\ne 0$. Thus we obtain a nice total-13-avd-coloring, a contradiction.

(2) Suppose to the contrary that $n_{5^-}(v)\ge 5$. Then $d(v_1)\le 2$, $d(v_2)\le 3$, $d(v_3)\le 4$ and $d(v_4) \le d(v_5)\le 5$. Let $H=G-vv_1-vv_2-\cdots -vv_5$. Thus there is a total-13-avd-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,\ldots ,v_5$ and denote this partial total-13-avd-coloring by $\phi '$. Let C denote the set of all colors used in $\phi '$ and let $S_{i}=C\setminus (C_{\phi '}(v)\cup C_{\phi '}(v_i))$ for $i=1,2,\ldots ,5$. Obviously, $|S_{1}|\ge 6$, $|S_{2}|\ge 5$, $|S_{3}|\ge 4$, $|S_{4}|\ge 3$ and $|S_{5}|\ge 3$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after $vv_1,vv_2,\ldots ,vv_5$ are colored. Let $s_1,s_2,\ldots ,s_5$ correspond to the colors of $vv_1,vv_2,\ldots ,vv_5$ respectively. Similar to Claim 2(1), $\phi$ is a nice total-13-avd-coloring, if there exist $s_i\in S_i,i=1,2,\ldots ,5$ such that $P(s_1,s_2,\ldots ,s_5)\ne 0$, where

$$\begin{aligned} P(x_1,x_2,\ldots ,x_5)=\prod _{1\le i<j\le 5}(x_i-x_j)\prod _{6\le i\le 10}\left( \sum _{t=1}^5 x_t+m_{\phi '}(v)-m_{\phi '}(v_i)\right) . \end{aligned}$$

By MATLAB, $c_P(x_1^{5}x_2^{4}x_3^{3}x_4^2x_5)=c_Q(x_1^{5}x_2^{4}x_3^{3}x_4^2x_5)=1$, where $Q(x_1,x_2,\ldots ,x_5)=\prod _{1\le i<j\le 5}(x_i-x_j)(\sum _{t=1}^5 x_t)^5$. According to Lemma 1, since $\deg (P)=15$, $|S_{1}|\ge 6$, $|S_{2}|\ge 5$, $|S_{3}|\ge 4$, $|S_{4}|\ge 3$ and $|S_{5}|\ge 3$, there exist $s_i\in S_{i},i=1,2,\ldots ,5$ such that $P(s_1,s_2,\ldots ,s_5)\ne 0$. Thus we obtain a nice total-13-avd-coloring, a contradiction.   $\square$

Suppose uv is an edge of G. We call u is strong neighbor of v, if $d(v)=10$, $d(u)=3$ and uv is incident with at least two 3-cycles. We use $n^G_{str}(v)$ to denote the number of strong neighbors of v in G.

Claim 6

Suppose v is a 10-vertex of G. If $n_{3^-}(v)\ge 4$ and $n^G_{str}(v)\ne 0$, then $n_{5^-}(v)=4$.

Fig. 2

Configurations in the proof of Claim 6

Proof

Let $v_1, v_2, \ldots , v_{10}$ be the neighbors of v with $d(v_1)\le d(v_2)\le \cdots \le d(v_{10})$.

Since $n_{3^-}(v)\ge 4$, if $n_{2^-}(v)\ne 0$, then $n_{5^-}(v)=4$ by Claim 5. So we assume $n_{2^-}(v)=0$. Suppose to the contrary that $n_{5^-}(v)\ge 5$. Then $d(v_1)=d(v_2)=d(v_3)=d(v_4)=3$ and $d(v_5)\le 5$. Assume $v_1$ is a strong neighbor of v and $v_x,v_y$ are common neighbors of v and $v_1$. Let $u_1,u_2$ be the neighbors of $v_2$ other than v and $w_1,w_2$ be the neighbors of $v_3$ other than v (see Fig. 2). Let $H=G-vv_1$. Thus there is a total-13-avd-coloring of H by the minimality of G. Erase the colors of $vv_2,vv_3,vv_4,vv_5,v_1,v_2,v_3,v_4,v_5$ and denote this partial total-13-avd-coloring by $\phi$. Let C denote the set of all colors used in $\phi$. Since $\phi (v_2u_1)\ne \phi (v_2u_2)$, without loss of generality, we assume $\phi (v_1v_x)\ne \phi (v_2u_1)$. Since $C\setminus (C_{\phi } (v)\cup \{\phi (v_2u_2)\})$ has at least six colors and then has at least six 5-element subsets, there exists at least one 5-element subset $C'$, such that $C_{\phi }(v)\cup C'$ is different from any $C_{\phi }(v_j),j=6,7,8,9,10$. Now we will color $vv_1,\ldots ,vv_5$ with $C'$ properly to obtain a nice total-13-avd-coloring of G, which is a contradiction.

Case 1 $\phi (v_1v_y)\not \in C'$. Since $d(v_5) \le 5$, $|C_{\phi } (v_5)|\le 4$, we can color $vv_5$ with a color $a_5 \in C'\setminus C_{\phi }(v_5)$. Since $d(v_i) \le 3$ for $3 \le i \le 4$, $|C_{\phi } (v_i)|=2$, we can color $vv_4$ with a color $a_4\in (C'\setminus \{a_5\})\setminus C_{\phi }(v_4)$ and color $vv_3$ with a color $a_3\in (C'\setminus \{a_5,a_4\})\setminus C_{\phi }(v_3)$. Notice that $\phi (v_1v_y)\not \in C'\setminus \{a_3,a_4,a_5\}$, $\phi (v_2u_2)\not \in C'\setminus \{a_3,a_4,a_5\}$ and $\phi (v_1v_x)\ne \phi (v_2u_1)$, therefore we can color $vv_1$ and $vv_2$ with $a_1$ and $a_2$ respectively such that $\{a_1,a_2\}=C'\setminus \{a_3,a_4,a_5\}$ and $a_1\ne \phi (v_1v_x),a_2\ne \phi (v_2u_1)$.

Case 2 $\phi (v_1v_y) \in C'$. Notice that $\phi (v_1v_y) \not \in C_{\phi } (v)$.

Case 2.1 $\phi (v_1v_y)\ne \phi (v_2u_1)$. We color $vv_5,vv_4,vv_3$ with $a_5,a_4,a_3$ successively such that $a_i \in (C'\setminus \{a_5,\ldots , a_{i+1}\})\setminus C_{\phi }(v_i)$ for $3 \le i \le 5$, and if there exists an $i\in \{3,4,5\}$ such that $\phi (v_1v_y)\in (C'\setminus \{a_5,\ldots , a_{i+1}\})\setminus C_{\phi }(v_i)$, then set $a_i=\phi (v_1v_y)$; If there exists an $i\in \{3,4,5\}$ such that $\phi (v_1v_y)\not \in (C'\setminus \{a_5,\ldots , a_{i+1}\})\setminus C_{\phi }(v_i)$ and $\phi (v_1v_x)\in (C'\setminus \{a_5,\ldots , a_{i+1}\})\setminus C_{\phi }(v_i)$, then set $a_i=\phi (v_1v_x)$. If $\{\phi (v_1v_y),\phi (v_1v_x)\}\ne C'\setminus \{a_5,a_4,a_{3}\}$, say $\phi (v_1v_y)\not \in C'\setminus \{a_5,a_4,a_{3}\}$, then similar to Case 1, we can color $vv_2$ and $vv_1$ with the colors in $C'\setminus \{a_5,a_4,a_{3}\}$ safely. So we only consider the case that $\{\phi (v_1v_y),\phi (v_1v_x)\}= C'\setminus \{a_5,a_4,a_{3}\}$. In this case, we have $\{\phi (v_1v_y),\phi (v_1v_x)\}\subseteq C_{\phi }(v_i)$ for every $i\in \{3,4,5\}$. Particularly, $C_{\phi }(v_3)=\{\phi (v_1v_y),\phi (v_1v_x)\}$. Assume $\phi (v_3w_1)=\phi (v_1v_x)$ and $\phi (v_3w_2)=\phi (v_1v_y)$. Now we erase the colors of $vv_3,vv_4,vv_5$.

Case 2.1.1 $\phi (v_1v_x)\ne \phi (vv_y)$. Firstly, we exchange the colors of $v_1v_y$ and $vv_y$. Since $\phi (v_1v_y) \not \in C_{\phi } (v)$, we obtain a partial total-13-avd-coloring, denoted by $\phi '$. We can find at least one set $C''\subseteq C \backslash (C_{\phi '} (v)\cup \{\phi '(v_2u_2)\})$ such that $|C''|=5$ and coloring $vv_1,\ldots ,vv_5$ with the colors in $C''$ (based on $\phi '$) will not lead to the conflicts of v with its neighbors. Observe $\phi '(v_3w_2)=\phi '(vv_y)\not \in C''$. We color $vv_i$ with a color $b_i \in (C''\setminus \{b_5,\ldots , b_{i+1}\})\setminus C_{\phi '}(v_i)$ for $4 \le i \le 5$, and then color $vv_1$ with a color $b_1\in (C''\setminus \{b_5,b_4\})\setminus C_{\phi '}(v_1)$. Since $\phi '(v_3w_2)\not \in C''$, $\phi '(v_2u_2)\not \in C''$ and $\phi '(v_3w_1)=\phi '(v_1v_x)\ne \phi '(v_2u_1)$, therefore we can color $vv_2$ and $vv_3$ with $b_2$ and $b_3$ respectively such that $\{b_2,b_3\}=C''\setminus \{b_1,b_4,b_5\}$ and $b_2\ne \phi '(v_2u_1),b_3\ne \phi '(v_3w_1)$.

Case 2.1.2 $\phi (v_1v_x)=\phi (vv_y)$. We exchange the colors of $v_1v_y$ and $vv_y$, and the colors of $v_1v_x$ and $vv_x$ at the same time. Since $\phi (v_1v_y) \not \in C_{\phi } (v)$ and $\phi (v_1v_x)\not \in C_{\phi }(v)\setminus \{\phi (vv_y)\}$, we obtain a partial total-13-avd-coloring $\phi ''$. We can find at least one set $\hat{C}\subseteq C \backslash (C_{\phi ''} (v)\cup \{\phi ''(v_2u_2)\})$ such that $|\hat{C}|=5$ and coloring $vv_1,\ldots ,vv_5$ with the colors in $\hat{C}$ (based on $\phi ''$) will not lead to the conflicts of v with its neighbors. Now we color $vv_i$ with a color $c_i \in (\hat{C}\setminus \{c_5,\ldots , c_{i+1}\})\setminus C_{\phi ''}(v_i)$ for $4 \le i \le 5$, and then color $vv_1$ with a color $c_1\in (\hat{C}\setminus \{c_5,c_4\})\setminus C_{\phi ''}(v_1)$. Since $\phi ''(v_2u_2)\not \in \hat{C}$, we can color $vv_2$ with a color $c_2\in (\hat{C}\setminus \{c_5,c_4,c_1\})\setminus C_{\phi ''}(v_2)$. Finally, we color $vv_3$. Since $\phi ''(v_3w_2)=\phi ''(vv_y)\not \in \hat{C}$ and $\phi ''(v_3w_1)=\phi ''(vv_x)\not \in \hat{C}$, we can find a color $c_3\in (\hat{C}\setminus \{c_5,c_4,c_1,c_2\})\setminus C_{\phi ''}(v_3)$ to color $vv_3$.

Case 2.2 $\phi (v_1v_y)=\phi (v_2u_1)$. Since $\phi (v_1u_y)\not \in C_{\phi } (v)$, we have $\phi (v_2u_1)\ne \phi (vv_x)$. If $\phi (v_1v_x)\ne \phi (vv_y)$, we only exchange the colors of $v_1v_y$ and $vv_y$, and if $\phi (v_1v_x)=\phi (vv_y)$, we exchange the colors of $v_1v_y$ and $vv_y$, and the colors of $v_1v_x$ and $vv_x$ at the same time. Denote the new partial total-13-avd-coloring by $\psi$. Then $\psi (v_1v_y)\ne \psi (v_2u_1)$, since $\phi (v_1v_x)\ne \phi (v_2u_1)$ and $\phi (vv_x)\ne \phi (v_2u_1)$, we claim that in both cases we have $\psi (v_1v_x)\ne \psi (v_2u_1)$. We can find at least one set $\tilde{C}\subseteq C \backslash (C_{\psi } (v)\cup \{\psi (v_2u_2)\})$ such that $|\tilde{C}|=5$ and coloring $vv_1,\ldots ,vv_5$ with the colors in $\tilde{C}$ (based on $\psi$) will not lead to the conflicts of v with its neighbors. If $\psi (v_1v_y)\not \in \tilde{C}$, it becomes Case 1. Otherwise it becomes Case 2.1. $\square$

3.2 Discharging process

We put all the 1-vertices and 2-vertices of G in $V_1$. Let $V_2=V\setminus V_1$ and $H=G[V_2]$. For H, we have the following result:

Claim 7

Let v be a vertex of H. Then the following properties hold:

• (1) $\delta (H)\ge 3$;

• (2) For any $k\in \{3,4,5\}$, $n^H_{k}(v)=n^G_{k}(v)$;

• (3) There is no edge $uv \in E(H)$ such that $d_H(v) \le 6$ and $d_H(u) \le 5$.

Proof

Let v be a vertex of H. If $d_G(v)\le 6$, then $n^G_{2^-}(v)=0$ by Claim 1. If $d_G(v)=7$, then $n^G_{2^-}(v)\le 1$ by Claim 2. If $d_G(v)=8$, then $n^G_{2^-}(v)\le 2$ by Claim 3. If $d_G(v)=9$, then $n^G_{2^-}(v)\le 3$ by Claim 4. If $d_G(v)=10$, then $n^G_{2^-}(v)\le 4$ by Claim 5. So we conclude that if $d_G(v)\le 5$, then $d_H(v)=d_G(v)$; If $d_G(v)\ge 6$, then $d_H(v)=d_G(v)-n^G_{2^-}(v)\ge 6$.

(1) Suppose to the contrary that there is a vertex $v\in V(H)$ such that $d_H(v)\le 2$. Obviously, $d_G(v)\ge 3$. If $d_G(v)\le 5$, then $d_H(v)=d_G(v)\ge 3$, if $d_G(v)\ge 6$, then $d_H(v)=d_G(v)-n^G_{2^-}(v)\ge 6$, which is a contradiction.

(2) Suppose u is a neighbor of v in H and $d_H(u)=k$, where $k\in \{3,4,5\}$. If $d_G(u)\ne k$, then we have $d_G(v)\ge 6$ by the above analysis, and then $d_H(v)\ge 6$, which is a contradiction. So $d_G(u)= k$ and $n^H_{k}(v)\le n^G_{k}(v)$. On the other hand, if u is a neighbor of v in G and $d_G(u)=k$, where $k\in \{3,4,5\}$, then $d_H(u)=k$ by the above analysis, so $n^G_{k}(v)\le n^H_{k}(v)$. Thus we conclude $n^H_{k}(v)=n^G_{k}(v)$.

(3) Suppose to the contrary that there is an edge $uv \in E(H)$ such that $d_H(v) \le 6$ and $d_H(u) \le 5$. Consider the degree of v in G. If $d_G(v)\le 6$, then $d_G(u)\ge 6$ by Claim 1, so $d_H(u)\ge 6$, a contradiction. If $d_G(v) =7$, then $n^G_{2^-}(v)=d_G(v)-d_H(v)\ge 1$. So $n^G_{5^-}(v)=n^G_{2^-}(v)=1$ by Claim 2, that means v has no other neighbors with degree less than 6 in G. Thus $d_G(u)\ge 6$, so $d_H(u)\ge 6$, a contradiction. Similarly, we can also can obtain a contradiction when $d_G(v) =8,9,10$ by Claims 3, 4 and 5. $\square$

Due to Claim 7, we obtain the following observation:

Observation 1

For any $f\in F(H)$, f is incident with at most $\lfloor \frac{d_H(f)}{2}\rfloor$ vertices of degree at most 5.

Observation 1 can be easily deduced from Claim 7,

Let uv be an edge of H and $d(u)=k$, we call u a bad k-neighbor of v if the edge uv belongs to two 3-faces, and call u a special k-neighbor of v if the edge uv belongs to exactly one 3-face. We use $N^H_{kb}(v)$ and $N^H_{ks}(v)$ to denote the number of bad k-neighbors and number of special k-neighbors of v in H respectively, and let $n^H_{kb}(v)=|N^H_{kb}(v)|$ and $n^H_{ks}(v)=|N^H_{ks}(v)|$.

Observation 2

Let v be a 10-vertex of H. Then

(1) $n^H_{3s}(v)\le 6$;

(2) $n^H_{3b}(v)+n^H_{4b}(v)+n^H_{5b}(v)\le \frac{1}{2}(10-n^H_{3s}(v))$.

Proof

(1) Suppose that $n^H_{3s}(v)\ge 7$. Then the number of 3-faces incident with v and its special 3-neighbors is at least 7. So v must incident with three consecutive such 3-faces. According to the definition of special 3-neighbors, the second 3-face can not incident with special 3-neighbors of v, a contradiction.

(2) Since H is planar graph, we use $v_0,v_1,\ldots , v_{9}$ to denote the neighbors of v in H in clockwise order. For $0\le i\le 9$, we call $v_i$ and $v_{j}$ consecutive if $j=i+1$ modulo 10. Notice that the number of neighbors of v which are not special 3-neighbors is at most $10-n^H_{3s}(v)$. Suppose that $n^H_{3b}(v)+n^H_{4b}(v)+n^H_{5b}(v)>\frac{1}{2}(10-n^H_{3s}(v))$, then there exist two consecutive vertices u and w such that $\{u,w\}\subseteq N^H_{3b}(v)\cup N^H_{4b}(v)\cup N^H_{5b}(v)$. According to the definition of bad k-neighbors, u must be incident with w, which is contradict with Claim 7(3).

Using Euler’s formula $|V (H)|-|E(H)| + |F(H)| = 2$ and the relation $\sum _{v\in V(H)}d_H(v)=\sum _{f\in F(H)}d_H(f)=2|E(H)|$, we have

$$\begin{aligned} \displaystyle {\sum _{v\in V(H)}}(d_H(v)-6)+\displaystyle {\sum _{f\in F(H)}}(2d_H(f)-6)=-12. \end{aligned}$$

That is

$$\begin{aligned} \displaystyle {\sum _{v\in V(H)}}(d_G(v)-n^G_{2^-}(v)-6)+\displaystyle {\sum _{f\in F(H)}}(2d_H(f)-6)=-12. \end{aligned}$$

We use the discharging method. First, we give an initial charge function $w(v) = d_G(v)-d^G_{2^-}(v)-6$ for every $v \in V (H)$, and $w(f) = 2d_H(f)-6$ for every $f \in F(H)$. Next, we design a discharging rule and redistribute weights accordingly. Let $w'$ be the new charge after the discharging. We will show that $w'(x)\ge 0$ for all $x \in V (H) \cup F(H)$. This leads to the following obvious contradiction:

$$\begin{aligned} 0\le \displaystyle {\sum _{x\in V(H)\cup F(H)}}w'(x)=\displaystyle {\sum _{x\in V(H)\cup F(H)}}w(x)=-12<0, \end{aligned}$$

hence demonstrates that no such a counterexample can exist.

The discharging rules are defined as follows:

R1 If v is a bad 3-neighbor of u in H, then u gives 1 to v.

R2 If v is a special 3-neighbor of u in H, then u gives $\frac{1}{2}$ to v.

R3 If v is a bad 4-neighbor of u in H, then u gives $\frac{1}{2}$ to v.

R4 If v is a bad 5-neighbor of u in H, then u gives $\frac{1}{5}$ to v.

R5 If $f\in F(H)$ is a 4-face, then f gives 1 to each incident $5^-$-vertex.

R6 If the degree of $f\in F(H)$ is at least 5, then f gives 2 to each incident $5^-$-vertex.

Now let us begin our analysis.

Let f be a face of H. Note that only vertices of degree at most 5 might receive weights from f. Suppose $d_H(f)=3$. Then no rule applies to f, so $w'(f)=0$. Suppose $d_H(f)=4$. Then there are at most two vertices of degree at most 5 on its boundary by Observation 1, so $w'(f)\ge 2\times 4-6-2=0$ by R5. Suppose $d_H(f)\ge 5$. Then $w'(f)\ge 2d_H(f)-6-2\lfloor \frac{d_H(f)}{2}\rfloor \ge 0$ by Observation 1 and R6.

Let v be a vertex of H. Obviously, $d_G(v)\ge d_H(v)\ge 3$.

Suppose $d_G(v)=3$. By Claim 1, $n^G_{5^-}(v)=0$ and $w(v)=-3$. Then we have $n^H_{5^-}(v)=0$ by Observation 1. So v gives no charge to its neighbors. We consider the faces incident with v in H. If v is incident with three 3-faces, then $w'(v)=-3+3=0$ by R1. If v is incident with exactly two 3-faces, then $w'(v)\ge -3+1+2\times \frac{1}{2}+1=0$ by R1, R2, R5 and R6. If v is incident with exactly one 3-face, then $w'(v)\ge -3+2\times \frac{1}{2}+2\times 1= 0$ by R2, R5 and R6. Otherwise, v is incident with three $4^+$-faces. So $w'(v)\ge -3+3\times 1=0$ by R5 and R6.

Suppose $d_G(v)=4$. By Claim 1, $n^G_{5^-}(v)=0$ and $w(v)=-2$. Then we have $n^H_{5^-}(v)=0$ by Observation 1. So v gives no charge to its neighbors. If all the faces incident with v are 3-faces, then $w'(v)\ge -2+4\times \frac{1}{2}=0$ by R3. If v is incident with exactly one $4^+$-face, then $w'(v)\ge -2+2\times \frac{1}{2}+1=0$ by R3, R5 and R6. Otherwise, v receives at least $2\times 1=2$ from the incident $4^+$-faces by R5 and R6, so $w'(v)\ge -2+2=0$.

Suppose $d_G(v)=5$. By Claim 1, $n^G_{5^-}(v)=0$ and $w(v)=-1$. Then we have $n^H_{5^-}(v)=0$ by Observation 1. So v gives no charge to its neighbors. If all the faces incident with v are 3-faces, then $w'(v)\ge -1+5\times \frac{1}{5}=0$ by R4. Otherwise, v receives at least 1 from the incident $4^+$-faces by R5 and R6, so $w'(v)\ge -1+1=0$.

Suppose $d_G(v)=6$. By Claim 1, $n^G_{5^-}(v)=0$ and $w(v)=0$. Then we have $n^H_{5^-}(v)=0$ by Observation 1. So v gives no charge to its neighbors. Thus $w'(v)=w(v)=0$.

Suppose $d_G(v)=7$. Then by Claim 2, if $n^G_{3^-}(v)\ge 1$, then $n^G_{5^-}(v)=1$, so $w'(v)\ge d_G(v)-6-n^G_{2^-}(v)-n^H_3(v)-n^H_4(v)-n^H_5(v)= 1-n^G_{5^-}(v)=0$ by Claim 7(2) and $R1-R4$. Otherwise, $n^G_{3^-}(v)=0$ and $n^G_{5^-}(v)\le 2$, and then $n^G_{2^-}(v)+n^H_3(v)=n^G_{3^-}(v)=0$ and $n^H_{4}(v)+n^H_{5}(v)=n^G_{5^-}(v)-n^G_{3^-}(v)\le 2$ by Claim 7(2). So $w'(v)\ge 7-6-\frac{1}{2}\times (n^H_{4}(v)+n^H_{5}(v))\ge 0$ by Claim 7(2) and R1–R4.

Suppose $d_G(v)=8$. According to Claim 3, Claim 7(2) and discharging rules, if $n^G_{3^-}(v)\ge 2$, then $n^G_{5^-}(v)=2$, $w'(v)\ge 8-6-n^G_{2^-}(v)-n^H_3(v)-n^H_4(v)-n^H_5(v)= 2-n^G_{5^-}(v)=0$; If $n^G_{3^-}(v)=1$, then $n^G_{5^-}(v)\le 3$, so $w'(v)\ge 8-6-(n^G_{2^-}(v)+n^H_3(v))-\frac{1}{2} (n^H_{4}(v)+n^H_{5}(v))=2-n^G_{3^-}(v)-\frac{1}{2} (n^G_{5^-}(v)-n^G_{3^-}(v))\ge 0$; If $n^G_{3^-}(v)=0$ and $n^G_4(v)\ge 1$, then $n^G_{5^-}(v)\le 3$, so $w'(v)\ge 8-6-n^G_{3^-}(v)-\frac{1}{2}(n^G_{5^-}(v)-n^G_{3^-}(v))> 0$; Otherwise, $n^G_{4^-}(v)=0$ and $n^G_{5}(v)\le 8$, so $w'(v)\ge 8-6-(n^G_{2^-}(v)+n^H_3(v)+n^H_4(v))-\frac{1}{5}n^H_5(v)=2-n^G_{4^-}(v)-\frac{1}{5}n^H_5(v)>0$.

Suppose $d_G(v)=9$. According to Claim 4, Claim 7(2) and discharging rules, if $n^G_{3^-}(v)\ne 0$ and $n^G_{4^-}(v)\ge 2$, then $n^G_{5^-}(v)\le 3$, so $w'(v)\ge 9-6-1\times n^G_{5^-}(v)\ge 0$; If $n^G_{3^-}(v)=1$ and $n^G_4(v)=0$, then $n^G_{5^-}(v)\le 6$, so $w'(v)\ge 9-6-(n^G_{2^-}(v)+n^H_3(v))-\frac{1}{2} n^H_{4}(v)-\frac{1}{5}n^H_{5}(v)=3-n^G_{3^-}(v)-\frac{1}{2}n^G_{4}(v)-\frac{1}{5}(n^G_{5^-}(v)-n^G_{4^-}(v))>0$; If $n^G_{3^-}(v)=0$ and $n^G_4(v)\ne 0$, then $n^G_{5^-}(v)\le 6$, so $w'(v)\ge 9-6-n^G_{3^-}(v)-\frac{1}{2} (n^G_{5^-}(v)-n^G_{3^-}(v))\ge 0$; Otherwise, $n^G_{4^-}(v)=0$ and $n^G_{5}(v)\le 9$, so $w'(v)\ge 9-6-n^G_{4^-}(v)-\frac{1}{5}n^G_5(v)>0$.

Suppose $d_G(v)=10$. We consider two cases.

Case 1 $n^G_{2^-}(v)\ne 0$. According to Claim 5, Claim 7(2) and discharging rules, if $n^G_{3^-}(v)\ge 2$ and $n^G_{4^-}(v)\ge 3$, then $n^G_{5^-}(v)\le 4$, so $w'(v)\ge 10-6-1\times n^G_{5^-}(v)\ge 0$; If $n^G_{3^-}(v)=2$ and $n^G_{4}(v)=0$, then $n^G_{5^-}(v)\le 7$, so $w'(v)\ge 10-6-n^G_{3^-}(v)-\frac{1}{2}n^G_{4}(v)-\frac{1}{5}(n^G_{5^-}(v)-n^G_{4^-}(v))>0$; If $n^G_{3^-}(v)=1$, then $n^G_{5^-}(v)\le 7$, so $w'(v)\ge 10-6-n^G_{3^-}(v)-\frac{1}{2} (n^G_{5^-}(v)-n^G_{3^-}(v))\ge 0$.

Case 2 $n^G_{2^-}(v)=0$. If $n^G_3(v)\le 3$, then $n^H_3(v)\le 3$ by Claim 7(2). According to Observation 2(2), $n^H_{3b}(v)+n^H_{4b}(v)+n^H_{5b}(v)\le \frac{1}{2}(10-n^H_{3s}(v))\le 5$. So $w'(v)\ge 10-6-(n^H_{3b}(v)+\frac{1}{2}(n^H_{3s}(v)+n^H_{4b}(v)+n^H_{5b}(v))) \ge 4-\frac{1}{2}(n^H_{3b}(v)+n^H_{3s}(v))-\frac{1}{2}(n^H_{3b}(v)+n^H_{4b}(v)+n^H_{5b}(v))\ge 4-\frac{1}{2}n^H_3(v)-\frac{1}{2}\times 5= \frac{1}{2}(3-n^H_3(v))\ge 0$ by $R1-R4$; If $n^G_{3}(v)\ge 4$ and $n^G_{str}(v)\ne 0$, then $n^G_{5^-}(v)=4$ by Claim 6. So $w'(v)\ge 10-6-(n^H_{3b}(v)+n^H_{3s}(v)+n^H_{4b}(v)+n^H_{5b}(v))\ge 4-n^H_{5^-}(v)\ge 4-n^G_{5^-}(v)=0$ by Claim 7(2) and $R1-R4$; Otherwise, $n^G_{3}(v)\ge 4$ and $n^G_{str}(v)=0$. Obviously, $n^H_{3b}(v)=0$. Since $n^H_{3s}(v)\le 6$ and $n^H_{4b}(v)+n^H_{5b}(v)\le \frac{1}{2}(10-n^H_{3s}(v))$ by Observation 2, $w'(v)\ge 10-6-\frac{1}{2}n^H_{3s}(v)-\frac{1}{2}(n^H_{4b}(v)+n^H_{5b}(v))\ge 4-\frac{1}{2}n^H_{3s}(v)-\frac{1}{2}\times \frac{1}{2}(10-n^H_{3s}(v))\ge \frac{1}{4}(6-n^H_{3s}(v))\ge 0$ by $R2-R4$.

This completes the whole proof of our theorem.

Appendix