The adjacent vertex distinguishing total coloring of planar graphs

Abstract

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by $\chi''_{a}(G)$.

In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with large maximum degree Δ by showing that if Δ≥14, then $\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2$, and $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of maximum degree.

1 Introduction

All graphs considered in this paper are simple and finite. A plane graph is a particular drawing of a planar graph on the Euclidean plane. Let V(G), E(G), F(G), Δ(G) (for short, Δ) and δ(G) denote the vertex set, edge set, face set, maximum degree and minimum degree of a given plane graph G, respectively. An element of G is a member of V(G)∪E(G)∪F(G). Any two elements are adjacent if they are either adjacent to or incident with each other in the traditional sense.

A total k-coloring of a graph G is a mapping ϕ:V(G)∪E(G)↦{1,2,…,k} such that any two adjacent elements in V(G)∪E(G) receive different colors. The total chromatic number, denoted by χ″(G), of a graph G is the smallest integer k such that G has a total k-coloring. Let C _ϕ (v)={ϕ(v)}∪{ϕ(xv)|xv∈E(G)} denote the set of colors assigned to a vertex v and those edges incident to v. We say that two adjacent vertices u and v conflict on ϕ if C _ϕ (u)=C _ϕ (v). A total k-coloring ϕ of G is adjacent vertex distinguishing, or it is a total-k-avd-coloring for short, if C _ϕ (u)≠C _ϕ (v) whenever uv∈E(G). The adjacent vertex distinguishing total chromatic number $\chi''_{a}(G)$ is the smallest integer k such that G has a total-k-avd-coloring.

By definition, it is evident that $\chi''_{a}(G)\geq \chi''(G)\geq \varDelta+1$ for any graph G. Zhang et al. (2005) proposed the following conjecture:

Conjecture 1

If G is a graph with at least two vertices, then $\chi''_{a}(G)\leq \varDelta+3$.

Chen (2008), and independently Wang (2007), confirmed Conjecture 1 for graphs G with Δ≤3. Later, Hulgan (2009) presented a more concise proof on this result. The adjacent vertex distinguishing total chromatic number of outerplane graphs was characterized completely in Wang and Wang (2010). Recently, a similar characterization for K ₄-minor free graphs was established in Wang and Wang (2009). Wang and Wang (2008) considered the adjacent vertex distinguishing total chromatic number of graphs with smaller maximum average degree.

Let χ(G) and χ′(G) denote the (vertex) chromatic number and the edge chromatic number of a graph G, respectively. As a direct consequence of definitions, we have the following relation:

Proposition 1

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

Suppose that G is a planar graph. Then χ(G)≤4 by the Four-Color Theorem (Appel and Haken 1976), and Δ≤χ′(G)≤Δ+1 by the Vizing’s Theorem (Vizing 1964). Therefore, $\chi_{a}''(G)\leq 4+\varDelta+1=\varDelta+5$. Huang and Wang (2012) proved the following:

Theorem 1

If G is a planar graph with Δ≥11, then $\chi''_{a}(G)\leq \varDelta+3$.

Another easy observation was made in Zhang et al. (2005):

Proposition 2

If G is a graph with two adjacent vertices of maximum degree, then $\chi_{a}''(G)\geq \varDelta+2$.

In this paper, we will characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with Δ≥14. In precise, we show the following:

Theorem 2

Let G be a planar graph with maximum degree Δ. Then the following hold.

(1) If Δ≥13, then $\chi''_{a}(G)\leq \varDelta+2$.

(2) If Δ≥14, then $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of degree Δ.

2 Notation

To prove our main result, we need to introduce some notations. Suppose that H is a subgraph of a given plane graph G. For x∈V(H)∪F(H), let d _H (x) denote the degree of x in H. In H, a vertex of degree k (at least k, at most k) is called a k-vertex (k ⁺ -vertex, k ⁻ -vertex). We use $N^{H}_{k}(x)$ to denote the set of k-vertices adjacent to x in H, and $d^{H}_{k}(x)=|N^{H}_{k}(x)|$. Similarly, we can define $d^{H}_{k^{+}}(x)$ and $d^{H}_{k^{-}}(x)$. For a face f∈F(H), we use b(f) to denote the boundary walk of f and write f=[u ₁ u ₂…u _m ] if u ₁,u ₂,…,u _m are the vertices of b(f) in clockwise order. Repeated occurrences of a vertex are allowed. The number of repeated occurrences of a vertex v on the boundary walk of f is called the multiplicity of v. A vertex x is small if 2≤d _H (x)≤5, otherwise it is big. A 4-cycle is bad if it has at least one 2-vertex, and is special if it has two 2-vertices. A 3-face is special if it is incident to a 2-vertex. A 2-vertex is special if it is adjacent to a special 4-cycle. A k-vertex x, with k≥3, is bad if each of the faces incident to it is either a 3-face, or a 4-face whose boundary forms a bad 4-cycle. We use $d^{H}_{k;b}(x)$ to denote the number of bad k-vertices adjacent to x. If there is no confusion in the context, we usually write $d_{G}(x),\ d^{G}_{k}(x), \ d^{G}_{k^{+}}(x),\ d^{G}_{k^{-}}(x),\ d^{G}_{k;b}(x), \varDelta(G)$ as $d(x),\ d_{k}(x), \ d_{k^{+}}(x),\ d_{k^{-}}(x),\ d_{k;b}(x), \varDelta$, respectively.

3 The upper bound Δ+2

Suppose that ϕ is a total-k-avd-coloring of a planar graph G using the color set C={1,2,…,k}, where k≥11. Assume that v∈V(G) with d(v)≤5 is not adjacent to any vertex of degree d(v). Since v has at most five adjacent vertices and five incident edges and |C|≥11, we may first erase the color of v and finally recolor it after arguing. In other words, we will omit the coloring for such vertices in the following discussion.

For positive integers p,q with p≤q, we use [p,q] to denote the set of all integers between p and q.

Theorem 3

If G is a planar graph with Δ≥13, then $\chi''_{a}(G)\leq \varDelta+2$.

Proof

Our proof proceeds by reductio ad absurdum. Assume that G is a counterexample to Theorem 3 such that |V(G)|+|E(G)| is as small as possible. Obviously, G is connected. Suppose that H=G−e for an edge e of G. If Δ(H)=Δ, then $\chi''_{a}(H)\leq \varDelta (H)+2=\varDelta+2$ by the minimality of G. If Δ(H)=Δ−1≥12, then $\chi''_{a}(H)\leq \varDelta(H)+3=\varDelta+2$ by Theorem 1. Therefore, we always have $\chi''_{a}(H)\leq \varDelta+2$. □

3.1 Unavoidable configurations

Claim 1

There is no edge uv∈E(G) such that d(v)≤7 and d(u)≤5.

Proof

Assume to the contrary that G contains an edge uv such that d(v)=t≤7 and d(u)=s≤5, and s≤t. Let H=G−uv. Then there is a total-(Δ+2)-avd-coloring ϕ of H with the color set C={1,2,…,Δ+2} by the above analysis. Since Δ≥13, we see |C|≥15.

Let u ₁,u ₂,…,u _s−1 be the neighbors of u other than v, and v ₁,v ₂,…,v _t−1 be the neighbors of v other than u. Suppose that ϕ(v)=1,ϕ(vv _i )=i+1 for i∈[1,t−1], and ϕ(u)=a ₁,ϕ(uu _i )=a _i+1 for i∈[1,s−1].

Case 1 s=t≤5.

Without loss of generality, we may assume that s=t=5. (For other cases, we have an easier proof.) If {a ₁,a ₂,…,a ₅}={1,2,…,5} or a ₁=1, then we may recolor u with a color in C∖{ϕ(u ₁),ϕ(u ₂),…,ϕ(u ₄),a ₁,a ₂,…,a ₅} such that u does not conflict with its neighbors. Thus, in what follows, we assume that {a ₁,a ₂,…,a ₅}≠{1,2,…,5} and a ₁≠1.

Subcase 1.1 Assume that at least two of a _i ’s belong to [1,5], say a _i ∈[1,8] for i=1,2,3,4,5. Suppose that uv cannot be colored. That is, C _ϕ (v _i )={1,2,3,4,5,i+8} and C _ϕ (u _j )={a ₁,a ₂,a ₃,a ₄,a ₅,j+12} for i=1,2,3,4, j=1,2,3. We recolor v with 13, and color uv with a color in {9,10,11,12} such that u does not conflict with u ₄.

Subcase 1.2 Assume that exactly one of a _i ’s belongs to [1,5], say a _i ∈[1,9] for i=1,2,3,4,5. Suppose that uv cannot be colored. That is, C _ϕ (v _i )={1,2,3,4,5,i+9} and C _ϕ (u _j )={a ₁,a ₂,a ₃,a ₄,a ₅,j+13} for i=1,2,3,4, j=1,2; or C _ϕ (v _i )={1,2,3,4,5,i+9} and C _ϕ (u _j )={a ₁,a ₂,a ₃,a ₄,a ₅,j+12} for i, j=1,2,3. For the first case, we recolor v with 14, and color uv with a color in {10,11,12,13} such that u does not conflict with u ₃,u ₄. For the second case, we recolor v with a color in {13,14} such that v does not conflict with v ₄, and color uv with a color in {10,11,12} such that u does not conflict with u ₄.

Subcase 1.3 Assume that a _i =i+5 for i=1,2,3,4,5. If there is c∈{7,8,9,10}∖{ϕ(v ₁),ϕ(v ₂),ϕ(v ₃),ϕ(v ₄)}, then we recolor v with c, and then reduce the proof to Subcase 1.2. Otherwise, {ϕ(v ₁),ϕ(v ₂),ϕ(v ₃),ϕ(v ₄)}={7,8,9,10}. Then we color uv with a color in {11,12,13,14,15} such that u does not conflict with its neighbors.

Case 2 s<t.

Then s≤5 and t≤7. We erase the color of u. By Case 1, d(u _i )≠d(u).

Without loss of generality, we may assume that a ₂,a ₃,…,a _s ∈[1,t+4]⊆[1,11]. Suppose that uv cannot be colored. That is, C _ϕ (v _i )={1,2,…,t,i+11} for i=1,2,3,4. We recolor v with a color in {t+1,…,t+4}∖{ϕ(v ₅),…,ϕ(v _t−1)}, and color uv with a color in {13,14,15} such that v does not conflict with v ₅,…,v _t−1. □

By Claim 1, we can remove all the colors of 5⁻-vertices in the following discussion.

Claim 2

Let v be a k-vertex of G with 8≤k≤9. If $d_{4^{-}}(v)\geq 1$, then $d_{6^{+}}(v)\geq 6$.

Proof

Let v ₁,v ₂,…,v _k be the neighbors of v with d(v ₁)≤4. Without loss of generality, we may assume that d(v ₁)=4, and u ₁,u ₂,u ₃ are the neighbors of v ₁ other than v. Note that d(u _i )≥8 by Claim 1 for i=1,2,3. Let H=G−vv ₁. Then there is a total-(Δ+2)-avd-coloring ϕ of H with the color set C={1,2,…,Δ+2}. Since Δ≥13, we see that Δ+2≥15. Let ϕ(v)=1, ϕ(vv _i )=i for i=2,3,…,k, and ϕ(v ₁ u ₁),ϕ(v ₁ u ₂),ϕ(v ₁ u ₃)∈[1,12]. We delete all the colors of 5⁻-vertices.

Suppose that $d_{6^{+}}(v)\leq 5$, and vv ₁ cannot be colored. So we may assume that ϕ(v _i )={1,2,…,k,11+i} for i=2,3,4. At most two neighbors of v other than v ₂,v ₃,v ₄ are of degree at least 6, say v ₅,v ₆. We recolor v with a color in {k+1,…,12}∖{ϕ(v ₅),ϕ(v ₆)}, and color vv ₁ with a color in {13,14,15} such that v does not conflict with v ₅,v ₆. □

Claim 3

Let v be a 10-vertex of G.

(1) If d ₁(v)≥1, then $d_{4^{-}}(v)\leq 1$.

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

Proof

Let v ₁,v ₂,…,v ₁₀ be the neighbors of v with d(v ₁)≤d(v ₂)≤⋯≤d(v ₁₀). If d(v ₁)=k≤3, we denote by u ₁,u ₂,…,u _k−1 the neighbors of v ₁ other than v. Note that u _i is of degree at least 8 by Claim 1. Let H=G−vv ₁, which admits a total-(Δ+2)-avd-coloring ϕ with the color set C={1,2,…,Δ+2}. We delete the colors of all 5⁻-vertices. Without loss of generality, we may assume that ϕ(v)=1, ϕ(vv _i )=i for i∈[2,10], and ϕ(v ₁ u _j )=a _j ∈[1,10+j]⊆[1,12] for j∈[1,k−1].

(1) Suppose to the contrary that $d_{4^{-}}(v)\geq 2$. Then d(v ₁)=1, d(v ₂)≤4, and v has at most 8 conflicting vertices. Suppose that vv ₁ cannot be colored, i.e., C _ϕ (v _11−i )={1,2,…,10,10+i} for i∈[1,5]. Without loss of generality, assume that 11∈{11,12,…,15}∖C _ϕ (v ₂). We recolor vv ₂ with 11, and color vv ₁ with a color in {12,13,14,15} such that v does not conflict with its neighbors.

(2) Let $d_{3^{-}}(v)=m\geq 1$. Suppose to the contrary that $d_{6^{+}}(v)\leq m+1$. Then v has at most m+1 conflicting vertices. First, vv ₁ can be colored with any color in {13,14,15}. Next, for each 2≤i≤m, vv _i can be recolored with a color b _i ∈{13,14,15}∖C _ϕ (v _i ), and vv ₁ can be colored with a color in {13,14,15}∖{b _i }. Hence we have at least 3+m−1=m+2 ways to recolor or color the edges adjacent to v. This implies that vv ₁ can be colored without conflict produced, a contradiction. □

Claim 4

Let v be a 11-vertex of G, and $d_{3^{-}}(v)=m$.

(1) If d ₁(v)≥1, then $d_{6^{+}}(v)\geq 5m-1$.

(2) If m≥1, then $d_{6^{+}}(v)\geq m+1$.

Proof

Let v ₁,v ₂,…,v ₁₁ be the neighbors of v with d(v ₁)≤d(v ₂)≤⋯≤d(v ₁₁). If d(v ₁)=k≤3, we denote by u ₁,u ₂,…,u _k−1 the neighbors of v ₁ other than v. Note that each u _i is of degree at least 8 by Claim 1. Let H=G−vv ₁, which admits a total-(Δ+2)-avd-coloring ϕ with the color set C={1,2,…,Δ+2}. We delete the colors of all 5⁻-vertices. Without loss of generality, we may assume that ϕ(v)=1, ϕ(vv _i )=i for i∈[2,11], and ϕ(v ₁ u _j )=a _j ∈[1,11+j]⊆[1,13] for j∈[1,k−1].

(1) Suppose to the contrary that $d_{6^{+}}(v)\leq 5m-2$. Then d(v ₁)=1, d(v ₂)≤⋯≤d(v _m )≤3. Firstly, vv ₁ can be colored with any color in {12,13,14,15}. Secondly, for each 2≤i≤m, there are at least two colors in {12,13,14,15}∖C _ϕ (v _i ), say 12 and 13. Then we recolor vv _i with 12, and color vv ₁ with one of 13,14,15; or we recolor vv _i with 13, and color vv ₁ with one of 14,15. Hence we have at least 5(m−1)+4=5m−1 ways to recolor or color the edges adjacent to v. Since $d_{6^{+}}(v)\leq 5m-2$, there exists at least one way to recolor or color the edges adjacent to v without conflict produced, a contradiction.

(2) Suppose to the contrary that $d_{6^{+}}(v)\leq m$. Then v has at most m conflicting vertices. Firstly, vv ₁ can be colored with any color in {14,15}. Secondly, for each 2≤i≤m, vv _i can be recolored with a color b _i in {12,13,14,15}∖C _ϕ (v _i ), and vv ₁ can be colored with a color in {14,15}∖{b _i }. Hence we have at least m+1 ways to recolor or color the edges adjacent to v, a contradiction. □

Claim 5

Let v be a 12-vertex of G, and $d_{3^{-}}(v)=m$.

(1) If d ₁(v)≥1, then $d_{6^{+}}(v)\geq 2m+1$.

(2) If d ₂(v)≥1, then $d_{6^{+}}(v)\geq m+1$.

(3) If d ₃(v)≥1, then $d_{6^{+}}(v)\geq 2$.

Proof

Let v ₁,v ₂,…,v ₁₂ be the neighbors of v with d(v ₁)≤d(v ₂)≤⋯≤d(v ₁₂). If d(v ₁)=k≤2, we denote by u ₁,…,u _k−1 the neighbors of v ₁ other than v. Note that u _i is of degree at least 8 by Claim 1. Let H=G−vv ₁, which admits a total-(Δ+2)-avd-coloring ϕ with the color set C={1,2,…,Δ+2}. We delete the colors of all 5⁻-vertices. Without loss of generality, we may assume that ϕ(v)=1, ϕ(vv _i )=i for i∈[2,12], and ϕ(v ₁ u _j )=a _j ∈[1,12+j]⊆[1,13] for j∈[1,k−1].

(1) Suppose to the contrary that $d_{6^{+}}(v)\leq 2m$. Then d(v ₁)=1, d(v ₂)≤⋯≤d(v _m )≤3. Firstly, vv ₁ can be colored with each color in {13,14,15}. Secondly, for each 2≤i≤m, vv _i can be recolored with a color b _i in {13,14,15}∖C _ϕ (v _i ), and then vv ₁ can be colored with a color {13,14,15}∖{b _i }. Hence we have at least 2(m−1)+3=2m+1 ways to recolor or color the edges adjacent to v, a contradiction.

(2) Suppose to the contrary that $d_{6^{+}}(v)\leq m$. Then v has at most m conflicting vertices. Firstly, vv ₁ can be colored with 14 or 15. Secondly, for each 2≤i≤m, vv _i can be recolored with a color b _i in {13,14,15}∖C _ϕ (v _i ), and vv ₁ can be colored with a color in {14,15}∖{b _i }. Hence we have at least m−1+2=m+1 ways to recolor or color the edges adjacent to v, a contradiction.

(3) It is obvious. □

Claim 6

Let v be k (≥13)-vertex of G with d ₁(v)≥1. Then $d_{6^{+}}(v)\geq 2$. Further, we have the following:

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

(2) If k=13, d ₁(v)=4, and $d_{4^{-}}(v)\geq 5$, then $d_{6^{+}}(v)\geq 6$.

Proof

Let $m=d_{3^{-}}(v)$. Let v ₁,v ₂,…,v _k be the neighbors of v with d(v ₁)=1, d(v ₂)≤d(v ₃)≤⋯≤d(v _m )≤3. Let H=G−vv ₁. Then there exists a total-(Δ+2)-avd-coloring ϕ of H with the color set C={1,2,…,Δ+2}. We delete all the colors of 5⁻-vertices and edges vv _i for 2≤i≤m, and denote this coloring by ϕ′.

It is easy to see that $d_{6^{+}}(v)\geq 2$. Assume to the contrary that $d_{6^{+}}(v)\leq 1$. Notice that |C _ϕ (v)|=k. Then vv ₁ can be colored with a color in C∖C _ϕ (v) without conflict produced, a contradiction.

(1) Suppose to the contrary that $d_{6^{+}}(v)\leq m$. That is, v has at most m conflicting vertices. Since Δ+2≥k+2, |C∖C _ϕ′(v)|≥k+2−(k+1−m)=m+1. Thus, there are at least ways to color vv ₁,vv ₂,…,vv _m . Hence, there exists a color set C′ with m colors, such that if we can recolor or color vv ₁,…,vv _m with colors in C′, then v will not conflict with its neighbors. Next, we color vv _m ,…,vv ₁ one-by-one with colors in C′ as follows: Since d(v _i )≤3 for 3≤i≤m, we color vv _i with color a _i in (C′∖{a _m ,…,a _i+1})∖C _ϕ (v _i ). Since d(v ₂)≤2, we color vv ₂ with color a ₂ in (C′∖{a _m ,…,a ₃})∖C _ϕ (v ₂). Since d(v ₁)=1, we color vv ₁ with color in C′∖{a _m ,…,a ₂}.

(2) Suppose to the contrary that $d_{6^{+}}(v)\leq 5$. That is, v has at most 5 conflicting vertices, say v ₉,v ₁₀,…,v ₁₃. Then d(v ₁)=d(v ₂)=d(v ₃)=d(v ₄)=1 and d(v ₅)≤4. Without loss of generality, assume that ϕ(v)=1 and ϕ(vv _i )=i for i=2,3,…,13. If {1,2,…,13,14} or {1,2,…,13,15} is not the color set of any neighbor of v, then we color vv ₁ with 14 or 15. Thus, assume that C _ϕ (v ₁₃)={1,2,…,13,14} and C _ϕ (v ₁₂)={1,2,…,13,15}. If there exists an i∈{2,3,4} such that {1,…,i−1,i+1,…,13,14,15} is not the color set of any neighbor of v, then we recolor vv _i with 14 and color vv ₁ with color 15. Assume that C _ϕ (v _13−i )={1,…,i−1,i+1,…,13,14,15} for i=2,3,4. We recolor vv ₅ with a color in {2,3,4,14,15}∖C _ϕ (v ₅), say a. If a=14 or 15, then we color vv ₁ with color {14,15}∖{a}. If a∈{2,3,4}, say a=2, then we recolor vv ₂ with 14 and color vv ₁ with 15. □

Claim 7

Let v be k-vertex of G with d ₁(v)=0 and d ₂(v)≥2. Assume that v ₁,v ₂,…,v _k are the neighbors of v with d(v ₁)=d(v ₂)=2, and u _i is the other neighbor of v _i for i=1,2. If the graph G−vv ₁ admits a total-(Δ+2)-avd-coloring ϕ such that ϕ(v ₁ u ₁)≠ϕ(v ₂ u ₂) or ϕ(v ₁ u ₁)∈C _ϕ (v), then $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1$.

Proof

Let $d_{3^{-}}(v)=m$. Suppose to the contrary that $d_{6^{+}}(v)\leq m$. Let ϕ(v)=1, ϕ(vv _i )=i for i∈[2,k]. For 1≤i≤m, if d(v _i )=2, we use α _i to denote the color in {k+1,k+2}∖C _ϕ (v _i ). If d(v _i )=3, we use β _i to denote the color in {2,k+1,k+2}∖C _ϕ (v _i ). The proof is split into the following two cases:

Case 1 ϕ(v ₁ u ₁)∈[1,k].

Note that vv ₁ can be colored with any color in {k+1,k+2}. And if d(v _i )=2, then vv _i can be recolored with α _i , and vv ₁ can be colored with a color in {k+1,k+2}∖{α _i }. Further, if d(v _i )=3, then we recolor vv _i with β _i . If β _i ∈{k+1,k+2}, then we color vv ₁ with a color in {k+1,k+2}∖{β _i }. If β _i =2, then we recolor vv ₂ with α ₂, and color vv ₁ with a color in {k+1,k+2}∖{α ₂}. Hence we have at least m+1 ways to recolor or color the edges adjacent to v, a contradiction.

Case 2 ϕ(v ₁ u ₁)≠ϕ(v ₂ u ₂).

By Case 1, we may assume that ϕ(v ₁ u ₁)=k+1, and ϕ(v ₂ u ₂)∈{1,2,…,k,k+2}.

Firstly, vv ₁ can be colored with k+2. Secondly, we can recolor vv ₂ with k+1, and color vv ₁ with 2 or k+2. Thirdly, for each 2-vertex v _i with i≥3, vv _i can be recolored with α _i . If α _i =k+1, then we color vv ₁ with k+2. If α _i =k+2, then we recolor vv ₂ with k+1 and color vv ₁ with 2. Lastly, for each 3-vertex v _i , we recolor vv _i with color β _i . If β _i =k+1, then we color vv ₁ with k+2. If β _i =k+2, then we recolor vv ₂ with k+1 and color vv ₁ with 2. If β _i =2, then we recolor vv ₂ with k+1 and color vv ₁ with k+2. Hence we have at least m−2+3=m+1 ways to recolor or color the edges adjacent to v, a contradiction. □

By Claim 7, we immediately have the following Claim 8.

Claim 8

If a k (≥13)-vertex v lies on a special 4-cycle, then $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1$.

Claim 9

If a k (≥13)-vertex v is incident to s (≥2) special 3-cycles, then $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1$.

Proof

Suppose to the contrary that $d_{6^{+}}(v)\leq d_{3^{-}}(v)$. Let f ₁,f ₂,…,f _s be the special 3-cycles incident to v. For 1≤i≤s, let vv _i u _i v be 3-cycle f _i where d(v _i )=2. By Claim 7, u ₁,u ₂,…,u _s are mutually distinct. Let H=G−vv ₁, which has a total-(Δ+2)-avd-coloring ϕ with the color set C={1,2,…,Δ+2}. We delete all the colors of 5⁻-vertices. Suppose that C _ϕ (v)={1,2,…,k}, ϕ(vv _i )=i,i=2,3,…,s and ϕ(vu _i )=s+i,i=1,2,…,s. By Claim 7, we may assume that ϕ(v ₁ u ₁)=⋯=ϕ(v _s u _s )=k+1. We switch the colors of vu ₂ and v ₂ u ₂. By Claim 7, $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1$, a contradiction. □

3.2 Discharging process

Let H be the graph obtained by removing all leaves of G. Then H is a connected plane graph with δ(H)≥2. By Claims 1–6, we display the relation between d(v) and d _H (v) in Table 1.

Table 1 The relation between d(v) and d _H (v)

Other properties of H are collected in the following Claim 10:

Claim 10

Let v be a vertex of H. Then the followings hold.

(0) If d _H (v)≤5, then d(v)=d _H (v).

(1) If d _H (v)≤6, then $d_{5^{-}}^{H}(v)=0$.

(2) If 7≤d _H (v)≤9 with $d_{4^{-}}^{H}(v)\geq 1$, then $d_{5^{-}}^{H}(v)\leq d_{H}(v)-6$.

(3) If d _H (v)=10 with $d_{3^{-}}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+2$.

(4) If d _H (v)=11 with $d_{3^{-}}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+1$.

(5) If d _H (v)=12 with $d_{2}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+1$. If d _H (v)=12 with $d_{3^{-}}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq 2$.

(6) If d _H (v)≥13 with $d_{2}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq 2$. Moreover, we have the following:

(i) If v lies on a special 4-cycle, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}(v)+1$.

(ii) If v is incident to s (≥2) special 3-faces, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}(v)+1$.

Proof

(0) Assume to the contrary that d(v)>d _H (v). Then v is adjacent to d(v)−d _H (v)≥1 leaves in G. By Claim 1, we see that d(v)≥8. If 8≤d(v)≤9, then d _H (v)≥6 by Claim 2, deriving a contradiction. If d(v)≥10, then d _H (v)≥7 by Table 1, therefore we also have a contradiction.

(1) If d(v)≤7, then $d_{5^{-}}(v)=0$ by Claim 1. Thus, $d_{5^{-}}^{H}(v)=0$ by (0). If 8≤d(v)≤9, then d ₁(v)≥2 or 3. By Claim 2, $d_{6^{+}}(v)\geq 6$, which implies that $d_{5^{-}}^{H}(v)=\nobreak0$.

(2) It is trivial for d(v)=d _H (v). Suppose that d(v)>d _H (v)≥7, so d ₁(v)>0. If d(v)≤9, then by Claim 2, $d_{6^{+}}(v)\geq 6$, which implies that $d_{5^{-}}^{H}(v)\leq d(v)-6$. If d(v)=10, then by Claim 3, $d_{4^{-}}(v)\leq 1$, which implies that $d_{4^{-}}^{H}(v)=0$. If d(v)=11, then d ₁(v)=11−d _H (v)≥2. By Claim 4(1), $d_{6^{+}}(v)\geq 5d_{3^{-}}(v)-1\geq \nobreak9$. Hence $d_{5^{-}}^{H}(v)\leq d_{H}(v)-6$. If d(v)=12, then d ₁(v)=12−d _H (v)≥3. By Claim 5(1), $d_{6^{+}}(v)\geq 2d_{3^{-}}(v)+1\geq 7$. Hence $d_{5^{-}}^{H}(v)\leq d_{H}(v)-6$. If d(v)=13, then d ₁(v)=d(v)−d _H (v)≥4. Since $d_{4^{-}}^{H}(v)\geq 1$, by Claim 6, $d_{6^{+}}(v)\geq 6$. Hence $d_{5^{-}}^{H}(v)\leq d_{H}(v)-6$. If d(v)≥14, then d ₁(v)≥5. By Claim 6, $d_{6^{+}}(v)\geq 6$, and hence $d_{5^{-}}^{H}(v)\leq d_{H}(v)-6$.

(3) It is trivial if d(v)=d _H (v). Suppose that d(v)>d _H (v), so d ₁(v)>0. It is easy to see that $d_{6^{+}}^{H}(v)=d_{6^{+}}(v)$, and $d_{3^{-}}^{H}(v)=d_{3^{-}}(v)-d_{1}(v)$. If d(v)=11, then by Claim 4, $d_{6^{+}}(v)\geq 5d_{3^{-}}(v)-1\geq d_{3^{-}}^{H}(v)+2$. If d(v)=12, then by Claim 5, $d_{6^{+}}(v)\geq 2d_{3^{-}}(v)+1\geq d_{3^{-}}^{H}(v)+2$. If d(v)≥13, then d ₁(v)≥3. By Claim 6, $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1\geq d_{3^{-}}^{H}(v)+2$.

(4)–(6) It is trivial by Claims 4–9. □

Using Euler’s formula |V(H)|−|E(H)|+|F(H)|=2, we have

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

(1)

In order to complete the proof, we make use of discharging method. First, we define an initial charge function w(v)=d _H (v)−6 for every v∈V(H), and w(f)=2d _H (f)−6 for every f∈F(H). Next, we design a discharging rule and redistribute weights accordingly. Once the discharging is finished, a new charge function w′ is produced. However, the sum of all charges is kept fixed when the discharging is in progress. Nevertheless, we can show that w′(x)≥0 for all x∈V(H)∪F(H). This leads to the following obvious contradiction:

$$0\leq \sum _{x\in V(H)\cup F(H)}w'(x)=\sum _{x\in V(H)\cup F(H)}w(x)=-12<0, $$

and hence demonstrates that no such a counterexample can exist.

The discharging rules are defined as follows:

(R1) Every 5⁺-face gives 2 to each incident small vertex (counting multiplicity).

(R2) Every 4-face f gives 2 to each incident 2-vertex if it is incident with exactly one 2-vertex. Otherwise, f gives 1 to each incident small vertex.

For every 5⁻-vertex u, let β(u) denote the total sum of charges transferred into u after (R1) and (R2) were carried out.

(R3) Every 7⁺-vertex gives $\frac{6-d_{H}(u)-\beta(u)}{d_{H}(u)}$ to each adjacent small vertex u.

Let τ(x→y) be the charge transferred from x to y. The following two observations can be easily deduced by Claim 10 and (R1)–(R3).

Observation 1

Every face f is incident to at most $\lfloor\frac{d_{H}(f)}{2}\rfloor$ 5⁻-vertices (counting multiplicity).

Observation 2

Let v be a 7⁺-vertex of H, and u be a 5⁻-vertex adjacent to v.

(1) Suppose that d _H (u)=2. If u is a special vertex, then $\tau(v\rightarrow u)\leq \frac{3}{2}$. Otherwise, τ(v→u)≤1.

(2) Suppose that d _H (u)=3. If u is bad, then τ(v→u)≤1. If u is adjacent to one 4-face that is not bad, then $\tau(v\rightarrow u)\leq \frac{2}{3}$. Otherwise, $\tau(v\rightarrow u)\leq \frac{1}{3}$.

(3) Suppose that d _H (u)=4. If u is bad, then $\tau(v\rightarrow u)\leq \frac{1}{2}$. Otherwise, $\tau(v\rightarrow u)\leq \frac{1}{4}$.

(4) Suppose that d _H (u)=5. Then $\tau(v\rightarrow u)\leq \frac{1}{5}$.

Observation 3

Let v be a 7⁺-vertex of H. If u is a vertex adjacent to v in H with $\tau(v\rightarrow u)=\frac{3}{2}$, then there exists a 2-vertex u′ such that $\tau(v\rightarrow u')\leq \frac{1}{2}$.

Proof

By (R1)–(R3), we see that d _H (u)=2 and u is incident to a 3-face and a 4-face f=[vuxy], whose boundary forms a special 4-cycle, that is d _H (y)=2. Let v ₁,v ₂,…,v _k be the neighbors of v in clockwise order such that x=v _k , u=v ₁, and y=v ₂, where k=d _H (v). By Claim 10, $d_{6^{+}}^{H}(v)\geq 2$. Let i be the least index such that d _H (v _i )≥3. Then 3≤i≤k−1 and d _H (v _i−1)=⋯=d _H (v ₁)=2. Let f _i−1 (respectively, f _i ) denote the face incident to vv _i−2 and vv _i−1 (respectively, vv _i−1 and vv _i ). Then d _H (f _i−1),d _H (f _i )≥4. By (R1) and (R2), τ(f _i−1→v _i−1)≥1 and τ(f _i →v _i−1)≥2. Therefore, $\tau(v\rightarrow v_{i-1})\leq \frac{1}{2}$. □

If x and y are two distinct neighbors of v in H with $\tau(v\to x)=\tau(v\to y)=\frac{3}{2}$, then by Observation 3 there exist x′ and y′ adjacent to v such that $\tau(v\to x')\leq \frac{1}{2}$ and $\tau(v\to y')\leq \frac{1}{2}$. It is easy to see that x′≠y′ by the proof of Observation 3. This fact and Observation 2 imply the following:

$$ \sum _{u\in N_2^H(v)}\tau(v\rightarrow u)\leq d_2^H(v). $$

(2)

Let w′ denote the resultant weight function after discharging was finished. It remains to verify that w′(x)≥0 for all x∈V(H)∪F(H).

Let f∈F(H). If d _H (f)≥5, then by (R1) and Observation 1,

$$w'(f)\geq w(f)-2\cdot\biggl\lfloor\frac{d_H(f)}{2}\biggr \rfloor=2d_H(f)-6-2\cdot\biggl\lfloor\frac {d_H(f)}{2}\biggr\rfloor \geq 0. $$

If d _H (f)=4, then f is incident with at most two small vertices by Observation 1. By (R2), f sends at most 2 to all adjacent 5⁻-vertices. Thus w′(f)≥w(f)−2=2⋅4−6−2=0.

Let v∈V(H) be a k-vertex. Then k≥2. Let v ₀,v ₂,…,v _k−1 denote the neighbors of v in clockwise order. For 0≤i≤k−1, we use f _i to denote the face incident to v with vv _i and vv _i+1 as boundary edges. In the following discussion, all indices are taken modulo k. We say that some vertices consecutive if they have consecutive indices on taken modulo k, i.e., v ₀ and v ₁ are consecutive vertices; v ₀ and v _k−1 are consecutive vertices.

If k≤5, then v is adjacent to no 6⁻-vertex in H by Claim 10(1). Hence, by (R1)–(R3), $w'(v)\geq k-6+\beta(v)+k\cdot\frac{6-k-\beta(v)}{k}=0$. If k=6, then by (R3), w′(v)=w(v)=k−6≥0. Otherwise, the proof is split into the following cases:

Case 1 7≤k≤9.

If $d_{4^{-}}^{H}(v)\geq 1$, then by Claim 10(2), $d_{5^{-}}^{H}(v)\leq k-6$. Hence, $w'(v)\geq w(v)-d_{5^{-}}^{H}(v)\geq k-6-(k-6)=0$ by Observation 2 and Eq. (2). If $d_{4^{-}}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\geq 2$, then $w'(v)\geq k-6-\frac{1}{5}(k-2)\geq 0$ by Observation 2. If $d_{4^{-}}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\leq 1$, then $w'(v)\geq k-6-2\cdot\frac{1}{5}>0$ by (R2).

Case 2 k=10.

Then w(v)=4. If $d_{3^{-}}^{H}(v)\geq 1$, then by Claim 10(3), $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+2$. Hence, $w'(v)\geq 4-d_{3^{-}}^{H}(v)-\frac{1}{2}(10-2d_{3^{-}}^{H}(v)-2)=0$ by Observation 2 and Eq. (2). If $d_{3^{-}}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\geq 2$, then $w'(v)\geq 4-\frac{1}{2}(10-2)=0$ by Observation 2. If $d_{3^{-}}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\leq 1$, then $w'(v)\geq 4-2\cdot\frac{1}{2}>0$ by (R2).

Case 3 k=11.

Then w(v)=5. If $d_{3^{-}}^{H}(v)\geq 1$, then by Claim 10(4), $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+1$. Hence, $w'(v)\geq 5-d_{3^{-}}^{H}(v)-\frac{1}{2}(11-2d_{3^{-}}^{H}(v)-1)=0$ by Observation 2 and Eq. (2). If $d_{3^{-}}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\geq 1$, then $w'(v)\geq 5-\frac{1}{2}(11-1)=0$ by Observation 2. If $d_{3^{-}}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)=0$, then w′(v)=4 by (R2).

Case 4 k=12.

Then w(v)=6. If $d_{3^{-}}^{H}(v)=0$, then $w'(v)\geq 6-\frac{1}{2}\cdot12=0$. If $d_{2}^{H}(v)\geq 1$, then by Claim 10(5), $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+1$. Hence, $w'(v)\geq 6-d_{3^{-}}^{H}(v)-\frac{1}{2}(12-2d_{3^{-}}^{H}(v)-1)>0$ by Observation 2 and Eq. (2).

Now assume that $d_{2}^{H}(v)=0$ and $d_{3}^{H}(v)\geq 1$. Note that, in this case, if u is a bad vertex adjacent to v then the faces incident to the edge uv is of degree 3. This implies that $d_{3;b}^{H}(v)\leq 6$ by Claim 10(1). If $d_{3;b}^{H}(v)=6$, then $d_{6^{+}}^{H}(v)=6$ by Claim 10(1), and hence $w'(v)\geq 6-d_{3;b}^{H}(v)=0$. So suppose that $d_{3;b}^{H}(v)\leq 5$. It is easy to observe that $d_{6^{+}}^{H}(v)\geq \max\{2,d_{3;b}^{H}(v)+1\}$. By Observation 2, we have:

$$ w'(v)\geq 6-d_{3;b}^H(v)-\frac{2}{3} \bigl(12-d_{3;b}^H(v)-d_{6^+}^H(v) \bigr)=\frac {2d_{6^+}^H(v)-d_{3;b}^H(v)-6}{3}. $$

(∗)

If $d_{3;b}^{H}(v)\geq 4$, or $d_{3;b}^{H}(v)=3$ and $d_{6^{+}}^{H}(v)\geq 5$, or $1\leq d_{3;b}^{H}(v)\leq 2$ and $d_{6^{+}}^{H}(v)\geq 4$, or $d_{3;b}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\geq 3$, then w′(v)≥0 by (∗).

If $d_{3;b}^{H}(v)=3$ and $d_{6^{+}}^{H}(v)\leq 4$, then $d_{6^{+}}^{H}(v)\geq \max\{2,d_{3;b}^{H}(v)+1\}=4$. Thus, $d_{6^{+}}^{H}(v)=4$. Since each bad 3-vertex in $N^{H}_{3;b}(v)$ must be adjacent to two 6⁺-vertices in N _H (v), then there are three consecutive 5⁻-vertices v _i ,v _i+1,v _i+2 in N _H (v). So both f _i and f _i+1 are of degree at least 4, and hence $\tau(v\rightarrow v_{i+1})\leq \frac{1}{3}$ by Observation 2. It follows that $w'(v)\geq 6-d_{3;b}^{H}(v)-\frac{2}{3}(12-d_{3;b}^{H}(v)-d_{6^{+}}^{H}(v)-1)-\frac{1}{3}=0$.

Assume that $1\leq d_{3;b}^{H}(v)\leq 2$ and $d_{6^{+}}^{H}(v)=3$. With a similar discussion to the above, there are four consecutive 5⁻-vertices v _i ,v _i+1,v _i+2,v _i+3 in N _H (v) such that $\tau(v\rightarrow v_{i+1})\leq \frac{1}{3}$ and $\tau(v\rightarrow v_{i+2})\leq \frac{1}{3}$ by Observation 2. Therefore, $w'(v)\geq 6-d_{3;b}^{H}(v)-\frac{2}{3}(12-d_{3;b}^{H}(v)-d_{6^{+}}^{H}(v)-2)-2\cdot \frac {1}{3}\geq 0$.

If $d_{3;b}^{H}(v)=1$ and $d_{6^{+}}^{H}(v)=2$, then there are five consecutive 5⁻-vertices v _i ,v _i+1,v _i+2,v _i+3, v _i+4 in N _H (v) such that $\tau(v\rightarrow v_{i+j})\leq \frac{1}{3}$ by Observation 2 for j=1,2,3. Therefore, $w'(v)\geq 6-d_{3;b}^{H}(v)-\frac{2}{3}(12-d_{3;b}^{H}(v)-d_{6^{+}}^{H}(v)-3)-3\cdot \frac{1}{3}=0$.

If $d_{3;b}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)=2$, then there are four consecutive 5⁻-vertices v _i ,v _i+1,v _i+2,v _i+3 in N _H (v) such that $\tau(v\rightarrow v_{i+1})\leq \frac{1}{3}$ and $\tau(v\rightarrow v_{i+2})\leq \frac{1}{3}$ by Observation 2. Consequently, $w'(v)\geq 6 -\frac{2}{3}(12 -d_{6^{+}}^{H}(v)-2)-2\cdot\frac{1}{3}=0$.

Case 5 k≥13.

We split the proof into the following possible cases.

Case 5.1 $d_{2}^{H}(v)\geq 1$.

By Claim 10(6), we have $d_{6^{+}}^{H}(v)\geq 2$, and so $d_{6^{+}}^{H}(v)+d_{2}^{H}(v)\geq 3$. If v lies on a special 4-cycle, then by Observation 2, Claim 10(6), and Eq. (2), we derive that $w'(v)\geq k-6-d_{3^{-}}^{H}(v)-\frac{1}{2}(k-2d_{3^{-}}^{H}(v)-1)\geq 0$.

Now assume that v does not lie on any special 4-cycle. Recall that s≥0 denotes the number of special 3-faces incident to v.

If s≥2, then by Observation 2, Claim 10(6), and Eq. (2), we have $w'(v)\geq k-\nobreak6-\nobreak d_{3^{-}}^{H}(v)-\frac{1}{2}(k-2d_{3^{-}}^{H}(v)-1)\geq 0$. So assume that 0≤s≤1. We note a fact that, for any $v_{i}\in N_{2}^{H}(v)$, if v _i is incident to a 3-face, then τ(v→v _i )≤1; otherwise, τ(v→v _i )=0 by (R1)–(R2). Thus, we have the following relation:

$$\sum _{x\in N_2^H(v)}\tau(v\rightarrow x)\leq s. $$

Using the previous result, we further get:

$$ \begin{array}[b]{lll} w'(v)&\geq & k-6-\bigl(s+d_3^H(v)+d_4^H(v)+d_5^H(v) \bigr) \cr\noalign{\vspace{3pt}} &\geq & k-6-\bigl(k-d_{6^+}^H(v)-\bigl(d_{2}^H(v)-s \bigr)\bigr). \end{array} $$

(∗∗)

Note that if [vxx′] is a special 3-face with d _H (x)=2, then d _H (x′)≥6 by Claim 10(1). Moreover, for any two special 3-faces [vxx′] and [vyy′] with d(x)=d(y)=2, we conclude that x′≠y′ since v does not lie on any special 4-cycle. Moreover, in the following proof, we write simply $N_{3,4,5}^{H}(v)=N_{3}^{H}(v)\cup N_{4}^{H}(v)\cup N_{5}^{H}(v)$.

• If $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)\geq 6$, then w′(v)≥k−6−(k−6)≥0 by (∗∗).

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=5$. If there are three consecutive vertices $v_{i},v_{i+1},v_{i+2}\in N_{3,4,5}^{H}(v)$, then $\sum_{j=i}^{i+2}\tau(v\to v_{j}) \leq \frac{2}{3}+\frac{1}{3}+\frac{2}{3}=\frac{5}{3}$ by (R1)–(R3). Thus, $w'(v)\geq k-6-\frac{5}{3}-(k-5-3)>0$. Otherwise, since k≥13, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(5+s)\geq 7$, there must be two vertex-disjoint subsets $\{v_{i},v_{i+1}\}, \{v_{j},v_{j+1}\}\subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $\tau(v\rightarrow v_{i})+\tau(v\rightarrow v_{i+1})+\tau(v\rightarrow v_{j})+\tau(v\rightarrow v_{j+1})\leq 4\cdot\frac{2}{3}=\frac{8}{3}$. It turns out that $w'(v)\geq k-6- \frac{8}{3}-(k-5-4)>0$.

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=4$. If there are four consecutive vertices v _i ,v _i+1,v _i+2, $v_{i+3}\in N_{3,4,5}^{H}(v)$, then $\sum_{j=i}^{i+3}\tau(v\to v_{j}) \leq 2\cdot\frac{2}{3}+2\cdot\frac{1}{3}=2$ by (R1)–(R3), and hence w′(v)≥k−6−2−(k−4−4)=0. If there are two vertex-disjoint subsets $\{v_{i},v_{i+1},v_{i+2}\}, \{v_{l}, v_{l+1}\}\subseteq N_{3,4,5}^{H}(v)$, then by (R1)–(R3), $\sum_{j=i}^{i+2}\tau(v\to v_{j}) \leq 2\cdot\frac{2}{3}+\frac{1}{3}=\frac{5}{3}$ and $\tau(v\to v_{l})+\tau (v\to v_{l+1})\leq \frac{2}{3}+\frac{2}{3}=\frac{4}{3}$. Hence $w'(v)\geq k-6-\frac{5}{3}-\frac{4}{3}-(k-4-5)=0$. Otherwise, since k≥13, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(4+s)\geq 8$, there are four vertex-disjoint subsets $\{v_{p},v_{p+1}\}, \{v_{q},v_{q+1}\}, \{v_{l},v_{l+1}\}, \{v_{m},v_{m+1}\} \subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $w'(v)\geq k-6-8\cdot\frac{2}{3}-(k-4-8)>0$.

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=3$. If there are six consecutive vertices v _i ,v _i+1,…, $v_{i+5}\in N_{3,4,5}^{H}(v)$, then $w'(v)\geq k-6-2\cdot\frac{2}{3}-4\cdot\frac{1}{3}-(k-3-6)>0$. If there are two vertex-disjoint subsets $\{v_{i},v_{i+1},\ldots,v_{i+4}\},\{v_{j},v_{j+1}\}\subseteq N_{3,4,5}^{H}(v)$, or $\{v_{i},v_{i+1},v_{i+2},v_{i+3}\},\{v_{j}, v_{j+1}, v_{j+2}\}\subseteq N_{3,4,5}^{H}(v)$, then $w'(v)\geq k-6-4\cdot\frac{2}{3}-3\cdot\frac{1}{3} -(k-3-7)>0$. Otherwise, since k≥13, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(4+s)\geq 9$, there are three vertex-disjoint subsets $\{v_{p},v_{p+1},v_{p+2}\}, \{v_{q},v_{q+1},v_{q+2}\}, \{v_{l},v_{l+1},v_{l+2}\} \subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $w'(v)\geq k-6-6\cdot\frac{2}{3}-3\cdot\frac{1}{3}-(k-3-9)>0$.

• Suppose that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=2$. Since $d_{2}^{H}(v)\geq 1$ and $d_{6^{+}}^{H}(v)\geq 2$, we see that s=1. If there are seven consecutive vertices $v_{i},v_{i+1},\ldots,v_{i+6}\in N_{3,4,5}^{H}(v)$, then $w'(v)\geq k-6-2\cdot\frac{2}{3}-5\cdot\frac{1}{3}-(k-2-7)=0$. Otherwise, since k≥13, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(2+s)\geq 10$, there are two vertex-disjoint subsets $\{v_{i},v_{i+1},\ldots,v_{i+4}\}, \{v_{j},v_{j+1},\ldots,v_{j+3}\} \subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $w'(v)\geq k-6-4\cdot\frac{2}{3}-5\cdot\frac{1}{3}-(k-2-9)>0$.

Case 5.2 $d_{2}^{H}(v)=0$ and $d_{3^{-}}^{H}(v)\geq 1$.

Note that, in this case, if u is a bad vertex adjacent to v then the faces incident to the edge uv is of degree 3. It is easy to see that $d_{3;b}^{H}(v)\leq \lfloor\frac{k}{2}\rfloor$ by Claim 10(1). If $d_{3;b}^{H}(v)=\lfloor\frac{k}{2}\rfloor$, then $d_{6^{+}}^{H}(v)=\lceil\frac{k}{2}\rceil$ by Claim 10(1). Thus, $w'(v)\geq k-6-d_{3;b}^{H}(v)=k-6-\lfloor\frac{k}{2}\rfloor \geq 0$. So assume that $d_{3;b}^{H}(v)\leq \lfloor\frac{k}{2}\rfloor-1$. Then $d_{6^{+}}^{H}(v)\geq d_{3;b}^{H}(v)+1$ if $d_{3;b}^{H}(v)>0$. Hence, by Observation 2,

$$ \everymath{\displaystyle} \begin{array}[b]{lll} w'(v)&\geq & k-6-d_{3;b}^H(v)- \frac{2}{3}\bigl(k-d_{3;b}^H(v)-d_{6^+}^H(v) \bigr) \cr\noalign{\vspace{3pt}} &=& \frac {1}{3}k-6-\frac{1}{3}d_{3;b}^H(v)+ \frac{2}{3}d_{6^+}^H(v). \end{array} $$

(∗∗∗)

If $d_{3;b}^{H}(v)\geq 3$, or $d_{3;b}^{H}(v)=2$ and $d_{6^{+}}^{H}(v)\geq 4$, or $0\leq d_{3;b}^{H}(v)\leq 1$ and $d_{6^{+}}^{H}(v)\geq 3$, then w′(v)≥0 by (∗∗∗).

If $d_{3;b}^{H}(v)=2$ and $d_{6^{+}}^{H}(v)=3$, then there are three consecutive vertices $v_{i},v_{i+1}, v_{i+2}\in N_{3,4,5}^{H}(v)$ such that $\tau(v\to v_{i+1})\leq \frac{1}{3}$ by Observation 2. Thus, $w'(v)\geq k-6-d_{3;b}^{H}(v)-\frac{2}{3}(k-d_{3;b}^{H}(v)-d_{6^{+}}^{H}(v)-1)-\frac {1}{3}\geq 0$.

If $d_{3;b}^{H}(v)=1$ and $d_{6^{+}}^{H}(v)=2$, then there are four consecutive vertices $v_{i},v_{i+1}, v_{i+2},v_{i+3}\in N_{3,4,5}^{H}(v)$ such that $\tau(v\to v_{i+1})\leq \frac{1}{3}$ and $\tau(v\to v_{i+2})\leq \frac{1}{3}$ by Observation 2. Thus, $w'(v)\geq k-6-d_{3;b}^{H}(v)-\frac{2}{3}(k-d_{3;b}^{H}(v)-d_{6^{+}}^{H}(v)-2)-2\cdot \frac {1}{3}\geq 0$.

If $d_{3;b}^{H}(v)=0$ and $1\leq d_{6^{+}}^{H}(v)\leq 2$, then there are five consecutive vertices v _i ,v _i+1,v _i+2, $v_{i+3},v_{i+4}\in N_{3,4,5}^{H}(v)$ such that $\tau(v\to v_{i+j})\leq \frac{1}{3}$ for j∈{1,2,3} by Observation 2. Thus, $w'(v)\geq k-6- \frac{2}{3}(k- d_{6^{+}}^{H}(v)-3)-3\cdot\frac{1}{3}\geq 0$.

If $d_{3;b}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)=0$, then $w'(v)\geq k-6-k\cdot\frac{1}{3}>0$.

Case 5.3 $d_{3^{-}}^{H}(v)=0$.

It is easy to inspect that $w'(v)\geq k-6-\frac{1}{2}k>0$ by Observation 2.

4 A characterization for Δ≥14

In this section, we will prove the following theorem.

Theorem 4

If G is a planar graph with Δ≥14 and without adjacent Δ-vertices, then $\chi''_{a}(G)=\varDelta+1$.

Proof

Assume that G is a counterexample to Theorem 4 such that |V(G)|+|E(G)| is as small as possible. Obviously, G is connected. Suppose that H=G−e for an edge e of G. By Theorem 3 or the minimality of G, we can deduce that $\chi''_{a}(H)\leq \varDelta+1$.

It is easy to inspect that Claims 1 to 5 in Sect. 3 still hold. With the similar discussion, the following Claims 6′–8′ can be shown.

Claim 6′

Let v be k-vertex of G with 13≤k<Δ, and d ₁(v)≥1. Then $d_{6^{+}}(v)\geq 2$. Further, we have the following:

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

(2) If k=13, d ₁(v)=4, and $d_{4^{-}}(v)\geq 5$, then $d_{6^{+}}(v)\geq 6$.

Claim 7′

If v is a vertex with 13≤d(v)<Δ which lies on a special 4-cycle, then $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1$.

Claim 8′

If v is a vertex with 13≤d(v)<Δ which is incident to s(≥2) special 3-faces, then $d_{6^{+}}(v)\geq d_{3^{-}}(v)+1$.

As G contains no adjacent Δ-vertices, no leaf is adjacent to a Δ-vertex.

Claim 9′

Let Δ≥14 and v be a Δ-vertex of G with d ₂(v)≥1. Then

(1) v does not lie on any special 4-cycle; and

(2) v is incident to at most one special 3-cycle.

Proof

(1) Suppose that v lies on a special 4-cycle vv ₁ uv ₂ v with d(v ₁)=d(v ₂)=2. Let H=G−vv ₁. Then there is a total-(Δ+1)-avd-coloring ϕ of H with the color set C={1,2,…,Δ+1}. Let C _ϕ (v)={1,2,…,Δ}, ϕ(v)=1, ϕ(vv ₂)=2, and ϕ(v _i u)=a _i for i=1,2. If a ₁∈[1,Δ], then we color vv ₁ with color Δ+1. If a ₁=Δ+1, then a ₂∈[1,Δ], we switch the colors of uv ₁ and uv ₂, and color vv ₁ with the color Δ+1. We always get a contradiction.

(2) Suppose that v is incident to at least two special 3-cycles, say vv ₁ v ₂ v and vv ₃ v ₄ v, where d(v ₁)=d(v ₃)=2. Let H=G−vv ₁. Then there is a total-(Δ+1)-avd-coloring ϕ of H with the color set C={1,2,…,Δ+1}. Let C _ϕ (v)={1,2,…,Δ}, ϕ(v)=1, ϕ(vv _i )=i for i=2,3,4, and ϕ(v _i v _i+1)=a _i for i=1,3. If a ₁∈[1,Δ], then we color vv ₁ with Δ+1. So assume that a ₁=Δ+1. If a ₃∈[1,Δ], we recolor vv ₃ with Δ+1, and color vv ₁ with 3. If a ₃=Δ+1, then we switch the colors of vv ₄ and v ₃ v ₄, and color vv ₁ with color 4. □

Let H be the graph obtained by removing all leaves of G. Then H is a connected plane graph with δ(H)≥2. By Claims 1–5 and 6′–9′, the relations shown in Table 1 in Sect. 3 holds for current d(v) and d _H (v).

The other properties of H are collected in the following Claim 10′. The proof is similar to that of Claim 10.

Claim 10′

Let v be a vertex of H. Then the followings hold.

(0) If d _H (v)≤5, then d(v)=d _H (v).

(1) If d _H (v)≤6, then $d_{5^{-}}^{H}(v)=0$.

(2) If 7≤d _H (v)≤9 with $d_{4^{-}}^{H}(v)\geq 1$, then $d_{5^{-}}^{H}(v)\leq d_{H}(v)-6$.

(3) If d _H (v)=10 with $d_{3^{-}}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+2$.

(4) If d _H (v)=11 with $d_{3^{-}}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+1$.

(5) If d _H (v)=12 with $d_{2}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}^{H}(v)+1$. If d _H (v)=12 with $d_{3^{-}}^{H}(v)\geq 1$, then $d_{6^{+}}^{H}(v)\geq 2$.

(6) Let v be a vertex with 13≤d _H (v)<Δ with $d_{2}^{H}(v)\geq 1$. Then $d_{6^{+}}^{H}(v)\geq 2$. Moreover, we have the following:

(i) If v lies on a special 4-cycle, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}(v)+1$.

(ii) If v is incident to s(≥2) special 3-faces, then $d_{6^{+}}^{H}(v)\geq d_{3^{-}}(v)+1$.

(7) Let v be a Δ-vertex with $d_{2}^{H}(v)\geq 1$. Then

(i) v does not lie on any special 4-cycle; and

(ii) v is incident to at most one special 3-face.

To derive a contradiction, we use the same rewritten Euler formula (1) and the initial charge function w(v)=d _H (v)−6 for every v∈V(H), and w(f)=2d _H (f)−6 for every f∈F(H). Then we design the same discharging rules (R1) to (R3). Now, Observations 1 and 2 still hold. It suffices to show that the new charge function w′ satisfies w′(x)≥0 for all x∈V(H)∪F(H). Indeed, this can be similarly proved for f∈F(G), or v∈V(G) with d _H (v)≤Δ−1. So assume that d _H (v)=Δ=k. Let v ₀,v ₁,…,v _k−1 denote the neighbors of v in clockwise order.

Case 1 $d_{2}^{H}(v)\geq 1$.

By Claim 10′(7), we may assume that v is adjacent to s special 3-faces with 0≤s≤1. For any $u\in N_{2}^{H}(v)$, if u is adjacent to a special 3-face, then τ(v→u)≤1; otherwise, τ(v→u)=0. Hence $\sum_{u\in N_{2}^{H}(v)}\tau(v\rightarrow u)\leq s$. Therefore,

$$ \everymath{\displaystyle} \begin{array}[b]{lll} w'(v) &\geq & k-6-\bigl(s+d_3^H(v)+d_4^H(v)+d_5^H(v) \bigr) \cr\noalign{\vspace{3pt}} &\geq & k-6-\bigl(k-d_{6^+}^H(v)-\bigl(d_{2}^H(v)-s \bigr)\bigr). \end{array} $$

(#)

• If $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)\geq 6$, then w′(v)≥k−6−(k−6)=0 by (#).

• Suppose that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=5$. If there are three consecutive vertices $v_{i},v_{i+1},v_{i+2}\in N_{3,4,5}^{H}(v)$, then $\sum_{j=i}^{i+2}\tau(v\to v_{j}) \leq \frac{2}{3}+\frac{1}{3}+\frac{2}{3}=\frac{5}{3}$ by (R1)–(R3). Thus, $w'(v)\geq k-6-\frac{5}{3}-(k-5-3)>0$. Otherwise, since k≥14, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(5+s)\geq 8$, there must be two vertex-disjoint subsets $\{v_{i},v_{i+1}\}, \{v_{j},v_{j+1}\}\subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $\tau(v\rightarrow v_{i})+\tau(v\rightarrow v_{i+1})+\tau(v\rightarrow v_{j})+\tau(v\rightarrow v_{j+1})\leq 4\cdot\frac{2}{3}=\frac{8}{3}$. It turns out that $w'(v)\geq k-6- \frac{8}{3}-(k-5-4)>0$.

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=4$. If there are four consecutive vertices v _i ,v _i+1,v _i+2, $v_{i+3}\in N_{3,4,5}^{H}(v)$, then $\sum_{j=i}^{i+3}\tau(v\to v_{j}) \leq 2\cdot\frac{2}{3}+2\cdot\frac{1}{3}=2$ by (R1)–(R3), and hence w′(v)≥k−6−2−(k−4−4)=0. Otherwise, since k≥14, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(4+s)\geq 9$, there are two vertex-disjoint subsets {v _i ,v _i+1,v _i+2}, $\{v_{j},v_{j+1}\}\subseteq N_{3,4,5}^{H}(v)$ such that $w'(v)\geq k-6-4\cdot\frac{2}{3}-\frac{1}{3}-(k-4-5)=0$.

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=3$. If there are six consecutive vertices v _i ,v _i+1,…, $v_{i+5}\in N_{3,4,5}^{H}(v)$, then $w'(v)\geq k-6-2\cdot\frac{2}{3}-4\cdot\frac{1}{3}-(k-3-6)>0$. Otherwise, since k≥14, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(4+s)\geq 10$, there are two vertex-disjoint subsets $\{v_{i},v_{i+1},\ldots,v_{i+4}\},\{v_{j},v_{j+1}\}\subseteq N_{3,4,5}^{H}(v)$, or $\{v_{i},v_{i+1},v_{i+2},v_{i+3}\},\{v_{j}, v_{j+1}, v_{j+2}\}\subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $w'(v)\geq k-6-4\cdot\frac{2}{3}-3\cdot\frac{1}{3} -(k-3-7)>0$.

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=2$. If there are seven consecutive vertices $v_{i},v_{i+1},\ldots,v_{i+6}\in N_{3,4,5}^{H}(v)$, then $w'(v)\geq k-6-2\cdot\frac{2}{3}-5\cdot\frac{1}{3}-(k-2-7)=0$. Otherwise, since k≥14, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(2+s)\geq 11$, there are two vertex-disjoint subsets $\{v_{i},v_{i+1},\ldots,v_{i+5}\}, \{v_{j},v_{j+1}\} \subseteq N_{3,4,5}^{H}(v)$. By (R1)–(R3), $w'(v)\geq k-6-4\cdot\frac{2}{3}-4\cdot\frac{1}{3}-(k-2-8)=0$.

• Assume that $d_{6^{+}}^{H}(v)+(d_{2}^{H}(v)-s)=1$. Since k≥14, $d_{3}^{H}(v)+d_{4}^{H}(v)+d_{5}^{H}(v)=k-(1+s)\geq 12$, there are nine consecutive vertices $v_{i},v_{i+1},\ldots,v_{i+8}\in N_{3,4,5}^{H}(v)$, then $w'(v)\geq k-6-2\cdot\frac{2}{3}-7\cdot\frac{1}{3}-(k-1-9)>0$.

Case 2 $d_{2}^{H}(v)=0$ and $d_{3}^{H}(v)\geq 1$.

Note that, in this case, if u is a bad vertex adjacent to v then the faces incident to the edge uv is of degree 3. Then $d_{3;b}^{H}(v)\leq \lfloor\frac{k}{2}\rfloor$ by Claim 10′(1). If $d_{3;b}^{H}(v)=\lfloor\frac{k}{2}\rfloor$, then $d_{6^{+}}^{H}(v)=\lceil\frac{k}{2}\rceil$ by Claim 10′(1). Hence, $w'(v)\geq k-6-d_{3;b}^{H}(v)=k-6-\lfloor\frac{k}{2}\rfloor \geq 0$. So assume that $d_{3;b}^{H}(v)\leq \lfloor\frac{k}{2}\rfloor-1$. Then $d_{6^{+}}^{H}(v)\geq d_{3;b}^{H}(v)+1$ if $d_{3;b}^{H}(v)>0$. If $d_{3;b}^{H}(v)\geq 2$, or $d_{3;b}^{H}(v)=1$ and $d_{6^{+}}^{H}(v)\geq 3$, or $d_{3;b}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\geq 2$, then by Observation 2,

Assume that $d_{3;b}^{H}(v)=1$ and $d_{6^{+}}^{H}(v)=2$. There are three consecutive vertices v _i ,v _i+1,v _i+2 $\in N_{3,4,5}^{H}(v)$ such that $\tau(v\rightarrow v_{i+1})\leq \frac{1}{3}$. Thus, $w'(v)\geq k-6-d_{3;b}^{H}(v)-\frac{2}{3}(k-d_{3;b}^{H}(v)-d_{6^{+}}^{H}(v)-1)-\frac {1}{3}\geq 0$.

Assume that $d_{3b}^{H}(v)=0$ and $d_{6^{+}}^{H}(v)\leq 1$. There are six consecutive vertices v _i ,v _i+1,…,v _i+5 $\in N_{3,4,5}^{H}(v)$ such that $w'(v)\geq k-6-\frac{2}{3}(k-d_{6^{+}}^{H}(v)-4)-4\cdot\frac{1}{3}\geq 0$.

Case 3 $d_{3^{-}}^{H}(v)=0$.

It is easy to see that $w'(v)\geq k-6-\frac{1}{2}k>0$.  □