The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven

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 or incident 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. An adjacent vertex distinguishing total-k-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 ^{\prime \prime }_{a}(G)$. It is known that $\chi _{a}^{\prime \prime }(G)\le \Delta (G)+3$ for any planar graph with $\Delta (G)\ge 10$. In this paper, we consider the list version of this coloring and show that if G is a planar graph with $\Delta (G)\ge 11$, then ${ ch}_{a}^{\prime \prime }(G)\le \Delta (G)+3$, where ${ ch}^{\prime \prime }_a(G)$ is the adjacent vertex distinguishing total choosability.

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 ^{\prime \prime }(G)$ of G is the smallest integer k such that G is total-k-colorable. It is obvious that $\chi ^{\prime \prime }(G)\ge \Delta (G)+1$ via Vizing’s Theorem (Vizing 1964). For this coloring, the following conjecture is well-known:

Conjecture 1

For any graph G, $\Delta (G)+1\le \chi ^{\prime \prime }(G)\le \Delta (G)+2$.

It has been known that this conjecture holds for graphs with maximum degree at most 5 (Kostochka 1996). For planar graphs, the only open case is for maximum degree 6 (Sanders and Zhao 1999).

In 2005, Zhang et al. (2005) proposed a new coloring, named adjacent vertex distinguishing total coloring. 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 for every edge $uv\in E(G)$, $C_{\phi }(v)\ne C_{\phi }(u)$, then $\phi$ is called adjacent vertex distinguishing total-k-coloring, or avdt-k-coloring for short. The smallest k for which G admits an avdt-k-coloring is called is called the adjacent vertex distinguishing total chromatic number, denoted by $\chi ^{\prime \prime }_{a}(G)$. It is obvious that $\chi ^{\prime \prime }_{a}(G)\ge \chi ^{\prime \prime }(G)\ge \Delta (G)+1$ and if a graph G contains two adjacent vertices of maximum degree, then $\chi ^{\prime \prime }_{a}(G)\ge \Delta (G)+2$. Zhang et al. (2005) studied adjacent vertex distinguishing total coloring of cycles, wheels, trees, complete graphs and complete bipartite graphs, then proposed the following conjecture:

Conjecture 2

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

Coker and Johannson (2012) used a probabilistic method to establish the upper bound $\Delta (G) + c$ for $\chi ^{\prime \prime }_{a}(G)$, where $c > 0$ is a constant. Later, Huang et al. (2012) proved that $\chi ^{\prime \prime }_{a}(G)\le 2\Delta (G)$ for any graph G with maximum degree $\Delta (G) \ge 3$. Chen (2008), and independently Wang (2007), proved the Conjecture 2 holds for graphs with maximum degree at most 3.

Let $\chi (G)$ and $\chi '(G)$ denote the vertex chromatic number and the edge chromatic number of G respectively. If we use the colors in $C_1=\{1,2,\ldots ,\chi (G)\}$ to color the vertices and use the colors in $C_2=\{\chi (G)+1,\chi (G)+2,\ldots ,\chi (G)+\chi '(G)\}$ to color the edges, we get an avdt-$(\chi (G)+\chi '(G))$-coloring. Thus we have the following relation:

Proposition 1

For any graph G, $\chi ^{\prime \prime }_{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 ^{\prime \prime }_{a}(G)\le \Delta (G)+5$. Particularly, since $\chi '(G)= \Delta (G)$ when $\Delta (G)\ge 7$ by Sanders and Zhao (2001), $\chi ^{\prime \prime }_{a}(G)\le \Delta (G)+4$. Actually, Conjecture 2 was confirmed for planar graphs with maximum degree at least 10 (Cheng et al. 2016) and planar graphs that contain no adjacent 4-cycles with maximum degree at least 8 (Sun et al. 2017). Furthermore, the bound can be improved to $\Delta (G)+2$ if G is a outerplanar graph (Wang and Wang 2010), a $K_4$-minor free graph (Wang and Wang 2009), a 2-degenerate graph with $\Delta (G)\ge 5$ (Miao et al. 2016), or a planar graph with maximum degree $\Delta (G) \ge 11$ (Yang et al. XXXX).

In this paper, we consider its list version. For a given graph G, let $L_x (x \in V \cup E)$ be a set of lists of real numbers, each of size k. The adjacent vertex distinguishing total choosability of G is the smallest k for which for any specified collection of such lists, there exists an adjacent vertex distinguish total coloring using colors from $L_x$ for each $x \in V \cup E$, and we denote it by ${ ch}^{\prime \prime }_a(G)$. We call such a coloring list adjacent vertex distinguishing total-k-coloring, or lavdt-k-coloring for short.

There are a few results known for this coloring. Qu et al. (2016) proved ${ ch}_{a}^{\prime \prime }(G)\le \Delta (G) +3$ if G is a planar graph with maximum degree $\Delta (G)\ge 13$. Wang et al. (2016) proved ${ ch}_{a}^{\prime \prime }(G)\le \Delta (G) +3$ if G is a planar graph without 4-cycles and with maximum degree $\Delta (G)\ge 7$. In this paper we will prove the following result:

Theorem 1

Let G be a planar graph with maximum degree $\Delta (G)\ge 11$. Then ${ ch}_{a}^{\prime \prime }(G)\le \Delta (G)+3$.

2 Notations and preliminaries

For a given plane 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 use $n_k (x$), $n_{k^+}(x)$ and $n_{k^-}(x)$ instead of $n^G_k (x)$, $n^G_{k^+}(x)$ and $n^G_{k^-}(x)$ respectively.

Suppose that $\phi$ is a lavdt-k-coloring of a graph G and $v\in V$. Let $C_{\phi }(v)$ be the set of the color of v and the colors of the edges incident with v and $m_{\phi }(v)$ be 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 are in 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}\ldots x_n^{k_n}$ in P is non-zero. If $S_1,\ldots , S_n$ are subsets of $\mathbb {F}$ with $|S_i| > k_i, i=1,\ldots ,n$, then there exist $s_1\in S_1,\ldots , s_n\in S_n$ so that $P(s_1, \ldots , s_n)\ne 0$.

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

Using Combinatorial Nullstellensatz, we obtain the following lemma, which is stated in Alon (1999):

Lemma 2

Let $S_i$ be a set of real numbers, where $|S_i|=l_i, i=1,2,\ldots ,t$ and $l_1\ge l_2\ge \cdots \ge l_t$. Let $S=\{\sum ^t_{i=1}x_i|x_i\in S_i,\prod _{1\le i<j\le t}(x_i-x_j)\ne 0\}$. Define $l'_1,l'_2,\ldots ,l'_t$ by $l'_1=l_1$ and $l'_i=\min \{l'_{i-1}-1,l_i\}$ for $2\le i\le t$. If $l'_t>0$, then

$$\begin{aligned} |S|\ge \sum ^t_{i=1}l'_t-\frac{1}{2}t(t+1)+1. \end{aligned}$$

3 Proof of the main theorem

Suppose G is a plane graph and is a counterexample of Theorem 1 such that $|V(G)|+|E(G)|$ is minimal and $k= \Delta +3\ge 14$. Obviously, G is connected. For each $x\in V(G)\cup E(G)$, let $L_x$ be an arbitrary set of k colors assigned to x.

3.1 Unavoidable configurations

Claim 1

Let v be a vertex of G with $d(v)\le 5$, then $n_{6^-}(v)=0$.

Proof

Suppose to the contrary that G contains an edge uv such that $d(v)=s\le 5$ and $d(u)=t\le 6$. Let $H=G-uv$. Then, by the minimality of G, there is a lavdt-k-coloring $\psi$ of H. Let $u_1,u_2,\ldots ,u_{t-1}$ be the neighbors of u other than v, and $v_1,v_2,\ldots ,v_{s-1}$ be the neighbors of v other than u.

Case 1

$t\le 5$. Without loss of generality, we assume that $s=t=5$ (We can get an easier proof for other cases). Erase the colors of u, v and denote this partial lavdt-k-coloring by $\phi '$. Let $S_{1}=L_u{\setminus } D_{\phi '}(u)$, $S_{2}=L_{uv}{\setminus }(C_{\phi '}(u)\cup C_{\phi '}(v))$ and $S_{3}=L_v{\setminus } D_{\phi '}(v)$. Then $|S_i|\ge 6$ for $i=1,2,3$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after u, uv, v are colored. Let $s_1,s_2,s_3$ correspond to the colors of u, uv, v respectively. 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$ is a lavdt-k-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) \left( x_1+m_{\phi '}(u)-(x_3+m_{\phi '}(v))\right) \nonumber \\&\quad \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}$$

By MATLAB, we obtain that $c_P\left( x_1^{4}x_2^{4}x_3^{4}\right) =c_Q\left( x_1^{4}x_2^{4}x_3^{4}\right) =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 6,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, we obtain a lavdt-k-coloring of G, which is a contradiction.

Case 2

$t=6$. Without loss of generality, assume that $s=5$ and $t=6$ (We can get an easier proof for other cases). Remove the colors of u, v and denote this partial lavdt-k-coloring by $\phi '$. Let $S_{1}=L_u{\setminus } D_{\phi '}(u)$, $S_{2}=L_{uv}{\setminus }(C_{\phi '}(u)\cup C_{\phi '}(v))$ and $S_{3}=L_v{\setminus } D_{\phi '}(v)$. Then $|S_1|\ge 4$, $|S_2|\ge 5$ and $|S_3|\ge 6$. Now we extend $\phi '$ to G and let $\phi$ denote the coloring after u, uv, v are colored. Let $s_1,s_2,s_3$ correspond to the colors of u, uv, v respectively. Since $d(u)\ne d(v)$, $C_{\phi }(u)\ne C_{\phi }(v)$. Similarly, for any $i\in \{1,2,3,4\}$, we have $d(v_i)\ne d(v)$ by Case 1 and so $C_{\phi }(v_i)\ne C_{\phi }(v)$. Hence $\phi$ is a lavdt-k-coloring if $s_1,s_2,s_3$ satisfy the following conditions:

• $s_i-s_j\ne 0$ for $1\le i<j\le 3$;

• $m_{\phi }(u)\ne m_{\phi }(u_i)$ for $i=1,2,3,4,5$.

Equivalently, $\phi$ is a lavdt-k-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)\prod _{i=1}^5 \left( x_1+x_2+m_{\phi '}(u)-m_{\phi '}(u_{i})\right) . \end{aligned}$$

By MATLAB, we obtain that $c_P\left( x_1^{2}x_2^{4}x_3^{2}\right) =c_Q\left( x_1^{2}x_2^{4}x_3^{2}\right) =-5\ne 0$, where $Q(x_1,x_2,x_3)=(x_1-x_2)(x_1-x_3)(x_2-x_3)(x_1+x_2)^5$. According to Lemma 1, since $\deg (P)=8$ and $|S_1|\ge 4$, $|S_2|\ge 5$, $|S_3|\ge 6$, 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, we obtain a lavdt-k-coloring of G, which is a contradiction. $\square$

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

Claim 2

If v is a 7-vertex of G, then $n_{5^-}(v)\le 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)$. Suppose to the contrary that $n_{5^-}(v)\ge 2$. Then $d(v_1)\le d(v_2)\le 5$. Let $H=G-vv_1-vv_2$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v,v_1,v_2$ and denote this partial lavdt-k-coloring by $\phi '$. Let $S_{i}=L_{vv_i}{\setminus }(C_{\phi }(v)\cup C_{\phi }(v_i))$ for $i=1,2$ and let $S_3=L_v{\setminus } D_{\phi '}(v)$. Obviously, $|S_{1}|\ge 5$, $|S_{2}|\ge 5$ and $|S_3|\ge 4$. Let $S=\left\{ \sum ^{3}_{i=1}x_i|x_i\in S_i,\prod _{1\le i<j\le 3}(x_i-x_j)\ne 0\right\}$. Using Lemma 2, we have

$$\begin{aligned} |S|\ge 5+4+3-\frac{1}{2}\times 3\times 4+1=7>5. \end{aligned}$$

Thus we can choose $s_1\in S_1$, $s_2\in S_2$ and $s_3\in S_3$ to color $vv_1$, $vv_2$ and v, respectively, such that v does not conflict with $v_3,v_4,v_5,v_6$ and $v_{7}$. Since $d(v)\ne d(v_i),1\le i\le 2$, we obtain a nice partial lavdt-k-coloring of G, which is a contradiction. $\square$

Claim 3

If v is an 8-vertex of G and $n_{4^-}(v)\ge 1$ then $n_{5^-}(v)\le 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)$ and $d(v_1)\le 4$. Suppose to the contrary that $n_{5^-}(v)\ge 3$. Then $d(v_2)\le d(v_3)\le 5$. Let $H=G-vv_1-vv_2-vv_3$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,v_3$ and denote this partial lavdt-k-coloring by $\phi$. Let $S_{i}=L_{vv_i}{\setminus }(C_{\phi }(v)\cup C_{\phi }(v_i))$ for $i=1,2,3$. Obviously, $|S_{1}|\ge 5$, $|S_{2}|\ge |S_3|\ge 4$. Let $S=\left\{ \sum ^{3}_{i=1}x_i|x_i\in S_i,\prod _{1\le i<j\le 3}(x_i-x_j)\ne 0\right\}$. Using Lemma 2, we have

$$\begin{aligned} |S|\ge 5+4+3-\frac{1}{2}\times 3\times 4+1=7>5. \end{aligned}$$

Thus for every $i\in \{1,2,3\}$, we can choose $s_i\in S_i$ to color $vv_i$ such that v does not conflict with $v_4,v_5,v_6,v_7$ and $v_{8}$. Since $d(v)\ne d(v_i),1\le i\le 3$, we obtain a nice partial lavdt-k-coloring of G, which is a contradiction. $\square$

Claim 4

If v is a 9-vertex of G, then $n_{5^-}(v)\le 6$; Moreover, if $n_{3^-}(v)\ge 1$, 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$. Then $d(v_1)\le d(v_2)\le \cdots \le d(v_7)\le 5$. Let $H=G-vv_1$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,\ldots ,v_{7},v$ and denote this partial lavdt-k-coloring by $\phi$. Since $|C_{\phi }(v)\cup C_{\phi }(v_1)|\le 8+4=12$, we can assign $vv_1$ a color $\beta$ from $L_{vv_1}{\setminus } \left( C_{\phi }(v)\cup C_{\phi }(v_1)\right)$. Then we color v. Observe that $|L_v{\setminus } \left( D_{\phi }(v)\cup \{\beta \}\right) |\ge 3$. We can assign v a color from $L_v{\setminus } \left( D_{\phi }(v)\cup \{\beta \}\right)$ such that v does not conflict with $v_8,v_{9}$. Since for any $i\in \{1,2,\ldots ,7\}$, $d(v_i)\ne d(v)$, the coloring we obtained is a nice partial lavdt-k-coloring, a contradiction.

• (2) Suppose $n_{3^-}(v)\ge 1$ and $n_{5^-}(v)\ge 4$. Then $d(v_1)\le 3$ 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 lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,v_3,v_4$ and denote this partial lavdt-k-coloring by $\phi$. Let $S_{i}=L_{vv_i}{\setminus }(C_{\phi }(v)\cup C_{\phi }(v_i))$ for $i=1,2,3,4$. Then $|S_{1}|\ge 6$, $|S_{2}|\ge |S_3|\ge |S_4|\ge 4$. Let $S=\left\{ \sum ^{4}_{i=1}x_i|x_i\in S_i,\prod _{1\le i<j\le 4}(x_i-x_j)\ne 0\right\}$. Using Lemma 2, we have

  $$\begin{aligned} |S|\ge 6+4+3+2-\frac{1}{2}\times 4\times 5+1=6>5. \end{aligned}$$

Thus for every $i\in \{1,2,3,4\}$, we can choose $s_i\in S_i$ to color $vv_i$ such that v does not conflict with $v_5,v_6,v_7,v_8$ and $v_9$. Since $d(v)\ne d(v_i),1\le i\le 4$, we obtain a nice partial lavdt-k-coloring of G, which is a contradiction. $\square$

Claim 5

Suppose v is a 10-vertex of G. If $n_{4^-}(v)\ge 1$ then $n_{5^-}(v)\le 8$. Moreover, if $n_{3^-}(v)\ge 1$ and $n_{4^-}(v)\ge 2$, 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_{4^-}(v)\ge 1$ and $n_{5^-}(v)\ge 9$. Then $d(v_1)\le 4$ and $d(v_2)\le \cdots \le d(v_9)\le 5$. Let $H=G-vv_1$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,\ldots ,v_{9},v$ and denote this partial lavdt-k-coloring by $\phi$. Since $|C_{\phi }(v)\cup C_{\phi }(v_1)|\le 9+3=12$, we can assign $vv_1$ a color $\beta \in L_{vv_1}{\setminus } \big (C_{\phi }(v)\cup C_{\phi }(v_1)\big )$. Then we color v. Observe that $|L_v{\setminus } \big (D_{\phi }(v)\cup \{\beta \}\big )|\ge 3$. We can assign v a color from $L_v{\setminus } \big (D_{\phi }(v)\cup \{\beta \}\big )$ such that v does not conflict with $v_{10}$. Since for any $i\in \{1,2,\ldots ,9\}$, $d(v_i)\ne d(v)$, the coloring we obtained is a nice partial lavdt-k-coloring, a contradiction.

• (2) Suppose that $n_{3^-}(v)\ge 1$, $n_{4^-}(v)\ge 2$ and $n_{5^-}(v)\ge 5$. Then $d(v_1)\le 3$, $d(v_2)\le 4$ and $d(v_3)\le d(v_4)\le d(v_5)\le 5$. Let $H=G-vv_1-vv_2-vv_3-vv_4-vv_5$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,v_3,v_4,v_5$ and denote this partial lavdt-k-coloring by $\phi$. Let $S_{i}=L_{vv_i}{\setminus }(C_{\phi }(v)\cup C_{\phi }(v_i))$ for $i=1,2,3,4,5$. Then $|S_1|\ge 6$, $|S_{2}|\ge 5$ and $|S_3|\ge |S_4|\ge |S_5|\ge 4$. Let $S=\left\{ \sum ^{5}_{i=1}x_i|x_i\in S_i,\prod _{1\le i<j\le 5}(x_i-x_j)\ne 0\right\}$. Using Lemma 2, we have

  $$\begin{aligned} |S|\ge 6+5+4+3+2-\frac{1}{2}\times 5\times 6+1=6>5. \end{aligned}$$

Thus for every $i\in \{1,2,3,4,5\}$, we can choose $s_i\in S_i$ to color $vv_i$ such that v does not conflict with $v_6,v_7,v_8,v_9$ and $v_{10}$. Since $d(v)\ne d(v_i),1\le i\le 5$, we obtain a nice partial lavdt-k-coloring of G, which is a contradiction. $\square$

Claim 6

Let v be a vertex of G. Suppose $d(v)=t\ge 11$ and $n_{2^-}(v)\ne 0$. Then

• (1) $n_{6^+}(v)\ge 2$;

• (2) If $n_{3^-}(v)\ge 2$ and $n_{4^-}(v)\ge 3$, then $n_{5^-}(v)\le t-6$.

Proof

Let $v_1, v_2, \ldots , v_{t}$ be the neighbors of v. Suppose $d(v_1)\le d(v_2)\le \cdots \le d(v_{t})$ and $d(v_1)\le 2$.

• (1) Suppose to the contrary that $n_{6^+}(v)\le 1$. We assume $d(v_1)\le d(v_2)\le \cdots \le d(v_{t-1})\le 5$. Let $H=G-vv_1$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,\ldots ,v_{t-1}$ and denote this partial lavdt-k-coloring by $\phi$. Since $|L_{vv_1}{\backslash }\big (C_{\phi }(v)\cup C_{\phi }(v_1)\big )|\ge 2$, we can assign $vv_1$ a color from $L_{vv_1}{\setminus } \big (C_{\phi }(v)\cup C_{\phi }(v_1)\big )$ such that v does not conflict with $v_{t}$. Since for any $i\in \{1,2,\ldots ,t-1)\}$, $d(v_i)\ne d(v)$, the coloring we obtained is a nice partial lavdt-k-coloring, a contradiction.

• (2) Suppose $n_{2^-}(v)\ge 1$, $n_{3^-}(v)\ge 2$, $n_{4^-}(v)\ge 3$ and $n_{5^-}(v)\ge t-5$. Then we have $d(v_1)\le 2, d(v_2)\le 3, d(v_3)\le 4$ and $d(v_4)\le \cdots \le d(v_{t-5})\le 5$. Let $H=G-\{vv_1,vv_2,\ldots , vv_{t-5}\}$. Then there exists a lavdt-k-coloring of H by the minimality of G. Erase the colors of $v_1,v_2,\ldots ,v_{t-5}$ and denote this partial lavdt-k-coloring by $\phi$. Let $S_i=L_{vv_i}{\setminus }(C_{\phi }(v)\cup C_{\phi }(v_i))$ for every $i\in \{1,2,\ldots ,t-5\}$. Then $|S_i|\ge k-(6+i)\ge t-3-i$ for $1\le i\le 3$, and $|S_i|\ge k-10\ge t-7$ for $4\le i\le t-5$. Let $S=\left\{ \sum ^{t-5}_{i=1}x_i|x_i\in S_i,\prod _{1\le i<j\le t-5}(x_i-x_j)\ne 0\right\}$. Using Lemma 2,

  $$\begin{aligned} |S|\ge \sum ^{t-5}_{i=1}(t-3-i)-\frac{1}{2}(t-5)(t-4)+1=t-4>5. \end{aligned}$$

So for every $i\in \{1,2,\ldots ,t-5\}$, we can choose $s_i$ from $S_i$ to color $vv_i$ such that v does not conflict with $d(v_{t-4}),d(v_{t-3}),d(v_{t-2}),d(v_{t-1}),d(v_{t})$. Thus we obtain a nice partial lavdt-k-coloring, which a contradiction. $\square$

3.2 Discharging process

Let H be the graph obtained by removing all the $2^-$-vertices of G. Obviously, H is a plane graph. 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 $l\in \{3,4,5\}$, $n^H_{l}(v)=n^G_{l}(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. According to Claims 1–6, if $d_G(v)\le 6$, then $n^G_{2^-}(v)=0$ and if $d_G(v)\ge 7$, then $n^G_{2^-}(v)\le d_G(v)-6$. So if $d_G(v)\le 5$, then $d_H(v)=d_G(v)$ and if $d_G(v)\ge 6$, then $d_H(v)=d_G(v)-n^G_{2^-}(v)\ge 6$.

• (1) Let v be a vertex of H. 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$. Thus we conclude $\delta (H)\ge 3$.

• (2) Suppose u is a neighbor of v in H and $d_H(u)=l$, where $l\in \{3,4,5\}$. If $d_G(u)\ne l$, 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)= l$ and $n^H_{l}(v)\le n^G_{l}(v)$. On the other hand, if u is a neighbor of v in G and $d_G(u)=l$, where $l\in \{3,4,5\}$, then $d_H(u)=l$ by the above analysis, so $n^G_{l}(v)\le n^H_{l}(v)$. Thus $n^H_{l}(v)=n^G_{l}(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$, by Claim 2, $n^G_{5^-}(v)=n^G_{2^-}(v)=1$; If $d_G(v) =8$, then $n^G_{2^-}(v)\ge 2$, by Claim 3, $n^G_{5^-}(v)=n^G_{2^-}(v)=2$; If $d_G(v) =9$, then $n^G_{2^-}(v)\ge 3$, by Claim 4, $n^G_{5^-}(v)=n^G_{2^-}(v)=3$; If $d_G(v) =10$, then $n^G_{2^-}(v)\ge 4$, by Claim 5, $n^G_{5^-}(v)=n^G_{2^-}(v)=4$; If $d_G(v) \ge 11$, then $n^G_{2^-}(v)\ge d_G(v)-6$, by Claim 6, $n^G_{5^-}(v)=n^G_{2^-}(v)=d_G(v)-6$. Thus when $d_G(v) \ge 7$, all the neighbors of v with degree less than 6 in G are $2^-$-vertices and don’t appear in H. Thus $d_G(u)\ge 6$, so $d_H(u)\ge 6$, a contradiction. $\square$

From Claim 7, we can easily deduce the following:

Observation 1

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

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

If u is a bad 3-neighbor of v in H, according to Claim 7(3), the degree of each common neighbor of u and v is at least 7, and thus at least 6. So we have:

Observation 2

Let v be a vertex of H. Then $n^H_{6^+}(v)\ge n^H_{3b}(v)$. Moreover, if $d_H(v)$ is odd, and $n^H_{6^+}(v)\ne 0$, then $n^H_{6^+}(v)\ge n^H_{3b}(v)+1$.

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 some discharging rules 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 counterexample for Theorem 1 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 of its incident $5^-$-vertices.

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

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 finally $d_H(f)\ge 5$. Then $w'(f)\ge 2d_H(f)-6-2\left\lfloor \frac{d_H(f)}{2}\right\rfloor \ge 0$ by Observation 1 and R6.

Let now v be a vertex of H. By Claim 7(1), $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 Claim 7(2). 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 Claim 7(2). 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 Claim 7(2). 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 Claim 7(2). So v gives no charge to its neighbors. Thus $w'(v)=w(v)=0$.

Suppose $d_G(v)=7$. Then by Claim 2, $n^G_{5^-}(v)\le 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)\ge 0$ by Claim 7(2) and R1-R4.

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

Suppose $d_G(v)=9$. According to Claims 4, 7(2) and discharging rules, if $n^G_{3^-}(v)\ne 0$ 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)=0$, then $n^G_{5^-}(v)\le 6$, so $w'(v)\ge 9-6-\left( n^G_{2^-}(v)+n^H_3(v)\right) -\frac{1}{2}\left( n^H_{4}(v)+n^H_{5}(v)\right) =3-n^G_{3^-}(v)-\frac{1}{2}\left( n^G_{5^-}(v)-n^G_{3^-}(v)\right) \ge 0$.

Suppose $d_G(v)=10$.

• if $n^G_{3^-}(v)\ne 0$ and $n^G_{4^-}(v)\ge 2$, then $n^G_{5^-}(v)\le 4$, so

  $$\begin{aligned} w'(v)\ge 10-6-1\times n^G_{5^-}(v)\ge 0. \end{aligned}$$

• If $n^G_{3^-}(v)=1$ and $n^G_4(v)=0$, then $n^G_{5^-}(v)\le 8$, so

  $$\begin{aligned} w'(v)\ge & {} 10-6-\left( n^G_{2^-}(v)+n^H_3(v)\right) -\frac{1}{2} n^H_{4}(v)-\frac{1}{5}n^H_{5}(v) \\= & {} 4-n^G_{3^-}(v)-\frac{1}{2}n^G_{4}(v)-\frac{1}{5}\left( n^G_{5^-}(v)-n^G_{4^-}(v)\right) \\> & {} 0. \end{aligned}$$

• If $n^G_{3^-}(v)=0$ and $n^G_4(v)\ne 0$, we also have $n^G_{5^-}(v)\le 8$, so

  $$\begin{aligned} w'(v)\ge 10-6-n^G_{3^-}(v)-\frac{1}{2} \left( n^G_{5^-}(v)-n^G_{3^-}(v)\right) \ge 0. \end{aligned}$$

• Otherwise, $n^G_{4^-}(v)=0$ and $n^G_{5}(v)\le 10$, so

  $$\begin{aligned} w'(v)\ge 10-6-n^G_{4^-}(v)-\frac{1}{5}n^G_5(v)>0. \end{aligned}$$

Now suppose $d_G(v)\ge 11$.

Case 1

$n^G_{2^-}(v)\ne 0$.

• If $n^G_{3^-}(v)\ge 2$ and $n^G_{4^-}(v)\ge 3$, then $n^G_{5^-}(v)\le d_G(v)-6$. So $w'(v)\ge d_G(v)-6-1\times n^G_{5^-}(v)\ge 0.$

• If $n^G_{3^-}(v)=2$ and $n^G_{4}(v)=0$, then $n^G_{6^+}(v)\ge 2$ and we have

  $$\begin{aligned} w'(v)\ge & {} d_G(v)-6-1\times n^G_{3^-}(v)-\frac{1}{5} \left( n^G_{5^-}(v)-n^G_{4^-}(v)\right) \\\ge & {} d_G(v)-6-1\times n^G_{3^-}(v)-\frac{1}{5}\left( d_G(v)-n^G_{6^+}(v)-n^G_{3^-}(v)\right) \\\ge & {} \frac{4d_G(v)-36}{5}>0. \end{aligned}$$

• If $n^G_{3^-}(v)=1$, then $n^G_{6^+}(v)\ge 2$ and we have

  $$\begin{aligned} w'(v)\ge & {} d_G(v)-6-1\times n^G_{3^-}(v)-\frac{1}{2}\left( n^G_{5^-}(v)-n^G_{3^-}(v)\right) \\\ge & {} d_G(v)-6-1\times n^G_{3^-}(v)-\frac{1}{2}\left( d_G(v)-n^G_{6^+}(v)-n^G_{3^-}(v)\right) \\\ge & {} \frac{d_G(v)-11}{2}\ge 0. \end{aligned}$$

Case 2

$n^G_{2^-}(v)=0$, then $d_G(v)=d_H(v)$.

• If $d_H(v)$ is even, we have $n^H_{6^+}(v)\ge n^H_{3b}(v)$ by Observation 2, and

  $$\begin{aligned} w'(v)\ge & {} d_G(v)-6-n^H_{3b}(v)-\frac{1}{2}\times \left( d_H(v)-n^H_{3b}(v)-n^H_{6^+}(v)\right) \\\ge & {} \frac{d_G(v)-12}{2}\ge 0. \end{aligned}$$

• If $d_H(v)$ is odd and $n^H_{6^+}(v)\ne 0$, we have $n^H_{6^+}(v)\ge n^H_{3b}(v)+1$ by Observation 2. Thus

  $$\begin{aligned} w'(v)\ge & {} d_G(v)-6-n^H_{3b}(v)-\frac{1}{2}\left( d_H(v)-n^H_{3b}(v)-n^H_{6^+}(v)\right) \\\ge & {} \frac{d_G(v)-11}{2}\ge 0. \end{aligned}$$

• If $d_H(v)$ is odd and $n^H_{6^+}(v)=0$, based on the defination of bad neighbors and special neighbors and Claim 7(3), $n^H_{3b}(v)+n^H_{3s}(v)+n^H_{4b}(v)+n^H_{5b}(v)=0$, so $w'(v)\ge d_G(v)-6>0$.

4 Open problem

Recently the adjacent vertex distinguishing total coloring by sums was also 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 neighbor sum distinguishing total-k-coloring. The smallest number k for which there exists such a neighbor sum distinguishing total-k-coloring is called the neighbor sum distinguishing total chromatic number, denoted by $\chi ^{\prime \prime }_{{ nsd}}(G)$. For this coloring, Pilśniak and Woźniak (2015) proposed the following conjecture:

Conjecture 3

For any graph G with at least two vertices, $\chi ^{\prime \prime }_{{ nsd}}(G)\le \Delta (G)+3$.

For more results, see Cheng et al. (2015), Ding et al. (2014), Dong and Wang (2014), Li et al. (2015, 2013), Ma et al. (2015), Qu et al. (2015). Similarly, we can define the list neighbor sum distinguishing total-k-coloring, and the smallest corresponding k is called the neighbor sum distinguishing total choosability, which is denoted by ${ ch}_{{ nsd}}^{\prime \prime }(G)$. Observe that ${ ch}_{a}^{\prime \prime }(G)\le { ch}_{{ nsd}}^{\prime \prime }(G)$. Now we propose the following open problem.

Problem 1

Let G be a planar graph with maximum degree $\Delta (G)\ge 11$. Is ${ ch}_{{ nsd}}^{\prime \prime }(G)\le \Delta (G)+3$ true?