# A Sufficient Condition for Planar Graphs of Maximum Degree 6 to be Totally 7-Colorable

Authors: Enqiang Zhu; Yongsheng Rao
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

A totalk-coloring of a graph is an assignment of k colors to its vertices and edges such that no two adjacent or incident elements receive the same color. The total coloring conjecture (TCC) states that every simple graph G has a total ΔG+2-coloring, where ΔG is the maximum degree of G. This conjecture has been confirmed for planar graphs with maximum degree at least 7 or at most 5, i.e., the only open case of TCC is that of maximum degree 6. It is known that every planar graph G of ΔG≥9 or ΔG∈7,8 with some restrictions has a total ΔG+1-coloring. In particular, in (Shen and Wang, 2009), the authors proved that every planar graph with maximum degree 6 and without 4-cycles has a total 7-coloring. In this paper, we improve this result by showing that every diamond-free and house-free planar graph of maximum degree 6 is totally 7-colorable if every 6-vertex is not incident with two adjacent four cycles or three cycles of size p,q,ℓ for some p,q,ℓ∈3,4,4,3,3,4.


---

## Body

## 1. Introduction

Throughout the paper, we consider only simple, finite, and undirected planar graphs and follow [1] for terminologies and notations not defined here. Given a graph G, we use VG and EG to denote the vertex set and the edge set of G, respectively. For a vertex v∈VG, we denote by dGv the degree of v in G and let NGv=uuv∈EG. A k-vertex, k−-vertex or k+-vertex is a vertex of degree k, at most k, or at least k, respectively. For a planar graph G, we always assume that G is embedded in the plane, and denote by FG the set of faces of G. The degree of a face f∈FG, denoted by dGf, is the number of edges incident with f, where each cut-edge is counted twice. A face of degree k, at least k, or at most k is called a k-face, k+-face, or k−-face. A k-face with consecutive vertices v1,v2,…,vk along its boundary in some direction is often said to be a dGv1,dGv2,…,dGvk-face. Two faces are called adjacent if they are incident with a common edge.A totalk-coloring of a graph G is a coloring from VG∪EG to 1,2,…,k such that no two adjacent or incident elements have the same color. A graph G is said to be totally k-colorable if it admits a total k-coloring. The total chromatic number of G, denoted by χtG, is the smallest integer k such that G is totally k-colorable. The total coloring conjecture (TCC), which was proposed by Behzad [2] and Vizing [3] independently, states that every simple graph G is totally ΔG+2-colorable, where ΔG is the maximum degree of G. TCC has been confirmed for graphs with the maximum degree at most 5 [4]. For planar graphs, it is known that every planar graph G with ΔG≥7 is ΔG+2-colorable [5]; in particular, if ΔG≥9, then χtG=ΔG+1 [6, 7]. Therefore, the only open case of TCC for planar graphs is the ones with maximum degree 6. As for this special kind of planar graphs, the first work was conducted by Wang et al. [8], who verified TCC for planar graphs with maximum degree 6 and without cycles of length 4. Sun et al. [7] improved the result by proving that every planar graph G with maximum degree 6 is totally 8-colorable if G contains no adjacent triangles. In [9], Zhu and Xu further improved this result by showing that every planar graph with maximum degree 6 is totally 8-colorable if the graph does not contain any subgraph isomorphic to a 4-fan.This paper mainly focuses on the sufficient conditions for planar graphs with maximum degree 6 to be totally 7-colorable. As for this topic, it has been proved thatχtG=7 if G does not contain 5-cycles [10] or 4-cycles [11]. We will show that every planar graph G with ΔG=6 has a total 7-coloring if G contains no some forbidden 4-cycles, which improves the result of [11].Theorem 1.
Suppose thatG is a planar graph with ΔG=6. If G does not contain a subgraph isomorphic to a diamond or a house, as shown in Figure 1, and every 6-vertex in G is not incident with two adjacent 4-cycles or 3-cycles with sizes p,q,ℓ for some p,q,ℓ∈3,4,4,3,4,4, then χtG=7.Figure 1
(a) Diamond. (b) House.
(a)
(b)


## 2. Reducible Configurations

LetH be a minimal counterexample to Theorem 1 in the sense that the quantity VH+EH is minimum. That is, H satisfies the following properties:(1)
H is a planar graph of maximum degree 6(2)
H contains no subgraph isomorphic to a diamond or a house.(3)
Every 6-vertex ofH is incident with neither two adjacent 4-cycles nor 3-cycles with sizes p,q,l for some p,q,ℓ∈3,4,4,3,4,4(4)
H is not totally 7-colorable such that VH+EH is minimum subject to (1), (2), and (3)Notice that every planar graph with maximum degree 5 is totally 7-colorable [4]. Additionally, it is easy to check that every subgraph of H also possesses (2) and (3). Therefore, every proper subgraph of H has total 7-coloring ϕ using the color set C=1,2,…,7.For a vertexv, we use Cϕv to denote the set of colors appearing on v and its incident edges, and C¯ϕv=1,2,…,7\Cϕv. This section is devoted to investigating some structural information, which shows that certain configurations are reducible, i.e., they cannot occur in H.Lemma 1.
(1)
Letuv be an edge of H such that dHu≤3 or dHv≤3. Then, dHu+dHv≥8(2)
The subgraph that is induced by all edges whose two ends are 2-vertex and 6-vertex, respectively, inH is a forest.The proof of Lemma1 can be found in [12].For any componentT of the forest stated in Lemma 1 (2), we can see that all leaves (i.e., 1-vertices) of T are 6-vertices. Therefore, T has maximum matching M that saturates every 2-vertex in T. For each 2-vertex v in T, we refer to the neighbor of v that is saturated by M as the master of v, see [13]. Clearly, for given M, each 6-vertex can be the master of at most one 2-vertex, and each 2-vertex has exactly one master.The following result follows from Lemma1 directly.Lemma 2.
Every 4-face inH is incident with at most one 2-vertex.Lemma 3.
Letf be a 3-face incident with a 2-vertex. Then, every 6-vertex incident with f has only one neighbor of degree 2.Proof.
Letv1 be the 2-vertex incident with f, and v2,v3 be the two 6-vertex incident with f. We first show that the result holds for v2 and then holds for v3 analogously. Assume to the contrary that v2 has another neighbor of degree 2, say u≠v1. Let ϕ be a total 7-coloring of H−v1v2 by the minimality of H. Erase the colors on v1 and u. Without loss of generality, we assume C¯ϕv2=7. If ϕv1v3≠7, then v1v2 can be properly colored with 7. Hence, H has a total 7-coloring by coloring v1,u properly (since v1,u are 2-vertices, there are at least three available colors for each of them) and a contradiction. So, we assume ϕv1v3=7. Let w=NHu\v2. When ϕuw≠7, we can color v1v2 with ϕv2u and recolor v2u with 7. When ϕuw=7, let ϕv2v3=x and ϕv2u=y. We first exchange the colors of v1v3 and v2v3 and then color v1v2 with y and recolor v2u with x. Therefore, we can obtain a 7-total-coloring of H by coloring v1,u with two available colors. This contradicts the assumption of H.Lemma 4.
H has no (4, 4, 4)-face.Proof.
Suppose thatH has a (4, 4, 4)-face with three incident vertices v1, v2, and v3. By the minimality of H, H−v1v2,v2v3,v3v1 has a total 7-coloring f. Erase the colors on vi for i=1,2,3. Clearly, each element in v1,v2,v3,v1v2,v2v3,v3v1 has at least three available colors. Therefore, f can be extended to a total 7-coloring of H, a contradiction.Lemma 5.
H has no (3, 5, 3, 5)-face.Proof.
Assume to the contrary thatH has (3, 5, 3, 5)-face f=v1v2v3v4, where dHv1=dHv3=3 and dHv2=dHv4=5. By the minimality of H, H−v1v2,v2v3,v3v4,v4v1 has total 7-coloring ϕ. Erase the colors on v1,v3. Clearly, each edge of v1v2,v2v3,v3v4,v4v1 has at least two available colors. Therefore, we can properly color edges v1v2,v2v3,v3v4 and v4v1. Additionally, since v1 and v3 are 3-vertices and they are not adjacent in H (because H contains no subgraph isomorphic to a diamond), we can properly color v1 and v3 with two available colors. Hence, we obtain a total 7-coloring of H and a contradiction.Lemma 6.
Every 6-vertex incident with a 2-vertex inH is adjacent to at most five 3−-vertices.Proof.
Letv be a 6-vertex incident with a 2-vertex v1 in H. Assume to the contrary that NHv contains six 3−-vertices. Let NHv=v1,v2,v3,v4,v5,v6, where dHv1=2,dHvi≤3 for i=2,3,4,5,6. By the minimality of H, H−vv1 has total 7-coloring ϕ. Without loss of generality, we assume C¯ϕv=7. Erase the colors on vi for i=1,2,3,4,5,6. If 7 does not appear on the edges incident with v1, then we can properly color vv1 with 7. Otherwise, we can properly color vv1 with ϕv by recoloring v with 7. Additionally, since v1,v2,v3,v4,v5,v6 are 3−-vertices, there is at least one available color for each of them, and by Lemma 1 (1), vivj∉EH for any i,j∈1,2,…,6, i≠j. Hence, we can obtain a 7-total-coloring of H and a contradiction.Lemma 7.
H contains no configurations depicted in Figure 2, where the vertices marked by • have no other neighbors in H.Figure 2
Three forbidden configurations inH.
(a)
(b)
(c)Proof.
For configuration (1), by the minimality ofH, H−vv1 has 7-total-coloring ϕ. Without loss of generality, we assume that Cϕv=1,2,3,4,5,6. If ϕv1u1≠7 (or ϕv2u2≠7), then we can properly color vv1 with 7 (or with ϕvv2 by recoloring vv2 with 7). If ϕv4u≠7, then we can properly color vv1 with ϕvv4 by recoloring vv4 with 7. So, we assume ϕu1v1=ϕu2v2=ϕuv4=7. Let ϕu1u2=c1. Obviously, c1≠7. If c1≠ϕvv2, then we can recolor u1u2 with 7, u1v1 with c1, u2v2 with c1, and then properly color vv1 with 7. If c1=ϕvv2, then c1≠ϕvv4. Therefore, we can safely interchange the colors of vv2 and vv4, recolor u1u2 with 7, u1v1 with c1, u2v2 with c1, and then properly color vv1 with 7. Thus, we obtain a 7-total-coloring of H and a contradiction.
For configuration (2), letϕ be a 7-total-coloring of H−vv1. Assume that Cϕv=1,2,3,4,5,6, where ϕvvi=i−1 for i=2,3,4,5,6, and ϕv=6. By a similar argument as in (1), we assume ϕu1v1=ϕu2v2=ϕu3v3=ϕuv5=7. Let ϕu1u2=c1 and ϕv2u3=c2. Obviously, c1,c2≠7. First, if c1∉1,c2, then we can recolor u1u2 with 7, u1v1 with c1, u2v2 with c1, and then properly color vv1 with 7. Second, if c1=1, then c1≠c2. When c2≠4, we can safely interchange the colors of vv2 and vv5, recolor u1u2 with 7, u1v1 with c1, u2v2 with c1, and then properly color vv1 with 7. When c2=4, we can safely interchange the colors of vv2 and vv3, recolor u1u2 with 7, u1v1 with c1, u2v2 with c1, and then properly color vv1 with 7. Third, if c1=c2, then c1≠1. When c1≠2, we can recolor u1u2 and v2u3 with 7, recolor u1v1, u2v2, and u3v3 with c1, and then properly color vv1 with 7. When c1=2, we can safely interchange the colors of vv3 and vv5, recolor u1u2 and v2u3 with 7, recolor u1v1, u2v2, and u3v3 with c1, and then properly color vv1 with 7. Hence, we obtain a 7-total-coloring of H and a contradiction.
For configuration (3), letϕ be a 7-total-coloring of H−vv1. Assume that Cϕv=1,2,3,4,5,6, where ϕvvi=i−1 for i=2,3,4,5,6, and ϕv=6. By a similar argument as in (1), assume that ϕu1v1=ϕu2v2=ϕu3v3=7. Let ϕu1u2=c1 and ϕu2v3=c2. Obviously, c1,c2≠7 and c1≠c2. If c1≠1, then we can recolor u1u2 with 7, u1v1 with c1, u2v2 with c1, and then properly color vv1 with 7. If c1=1, then c2≠1. Therefore, we can recolor u1u2 with 7, u1v1 with c1, u2v2 with c2, u2v3 with c1, and then properly color vv1 with 7. So, we obtain a 7-total-coloring of H and a contradiction.


## 3. Discharging

In this section, to complete the proof of Theorem1, we will use the discharging method to derive a contradiction. For a vertex v, we denote by n3v and n4v (or simply by n3 and n4) the number of 3-faces and 4-faces incident with v, respectively. For a face f, we denote by m2f and m3f (or simply by m2 and m3) the number of 2-vertices and 3-vertices incident with f, respectively.According to Euler’s formulaVH−EH+FH=2, we have(1)∑v∈VHdHv−4+∑f∈FHdHf−4=−8<0.Now, we definecx to be the initial charge of x∈VH∪FH. Let cx=dHx−4 for each x∈VH∪FH. Obviously, ∑x∈VH∪FHchx=−8<0. Then, we apply the following rules to reassign the initial charge that leads to a new charge c′x. If we can show that c′x≥0 for each x∈VH∪FH, then we obtain a contradiction and complete the proof. The discharging rules are defined as follows:(R1): from eachk-vertex to each of its incident k′-face f, transfer1/3 if k∈5,6, k′=3, and f is a 5+,5+,5+-face1/2 if k∈5,6, k′=3, and f is a 4−,5+,5+-face or 4−,4−,5+-face1/5 if k=5, k′=4, and f is incident with a 2-vertex or 3-vertex(R2): from each 6-vertex to each of its incident 4-facef, transfer1/4 if f is a 2,6,4+,6-face5/12 if f is a (2,6,3,6)-face2/15 if f is a 3,5+,5+,5+-face or (3,6,4,5)-face1/6 if f is a (3,6,4,6)-face1/3 if f is a (3,6,3,6)-face7/15 if f is a (3,6,3,5)-face(R3): from each 6-vertexu to each of its adjacent 2-vertex v, transfer1/2 if v is incident with a 3-face4/5 if v is not incident with a 3-face and u is a master of v1/5 if v is not incident with a 3-face and u is not a master of v(R4): from each 4-face to each of its adjacentk-vertex v, transfer1/2 if k=2 and v is not incident with a 3-face1/3 if k=3 and v is not incident with a 3-face(R5): from each5+-face to each of its adjacent k-vertex v, transfer1 ifk=2 and v is incident with a 3-face1/2 if k=2 and v is not incident with a 3-face1/2 if k=3 and v is incident with a 3-face1/3 if k=3 and v is not incident with a 3-face(R6): each5+-face transfers 1/6 to its adjacent (4−,4−,5+)-face(R7): every4+-face with positive charge after R1 to R6 transfers its remaining charges evenly among its incident 6-vertices.The rest of this article is to check thatc′x≥0 for every x∈VH∪FH.


## 4. Final Charge of Faces

Letf be a face of H. Suppose that f is a 3-face. By Lemma 1 (1) and Lemma 4, it follows that f is incident with at most two 4−-vertices. If f is incident with at most one 4−-vertex, then by (R1), c′f=3−4+3×1/3=0 or c′f=3−4+2×1/2=0. If f is incident with two 4−-vertices, then by (R1) and (R6), c′f=3−4+1/2+3×1/6=0.Suppose thatf is a 4-face. Clearly, f is not adjacent to a 3-face since H does not contain any subgraph isomorphic to a house. If f is incident with neither a 2-vertex nor a 3-vertex, then c′f=cf=0; if f is incident with a 2-vertex, then f is a (2, 6, 3+, 6)-face by Lemma 1 (1) and Lemma 2, and the 2-vertex is not incident with any 3-face (since H contains no subgraph isomorphic to a diamond). So, by (R2), (R4), and (R7), c′f=2×5/12−1/2−1/3=0 (when f is incident with a 3-vertex) or c′f=2×1/4−1/2=0 (when f is not incident with any 3-vertex); if f is not incident with a 2-vertex but is incident with a 3-vertex, then f is either a 3,5+,4+,5+-face or a 3, 3,5+,3,6-face by Lemma 1 (1) and Lemma 5. For the former case, after (R1), (R2), and (R4), f has at least 3×2/15−1/3=1/15 (when f is 3,5+,5+,5+-face) or 1/5+2/15−1/3=0 (when f is 3,5+,4,5-face) or 2×1/6−1/3=0 (when f is (3, 6, 4, 6)-face). Therefore, c′f≥0 by (R7). For the latter case, c′f=1/5+7/15−2×1/3=0 by (R1), (R2), (R4), and (R7) (when f is (3, 5,3,6)-face), or c′f=1/3+1/3−2×1/3=0 by (R2), (R4), and (R7) (when f is 3,6,3,6-face).Suppose thatf is a 5-face. Since H does not contain any subgraph isomorphic to a house, it has that every 2-vertex incident with it is not incident with a 3-face. Obviously, m2+m3≤2. If m2+m3≤1, then f has at least 5−4−1/2m2+m3−1/65−2m2+m3≥0 after R5 to (R6), and hence, c′f≥0 by R7. If m2+m3=2, then f is not adjacent to any 4−,4−,5+-face. Hence, f has at least 5−4−1/2m2+m3=0 after R5 to (R6), and c′f≥0.Suppose thatf is a 6-face. Then, at most one 2-vertex incident with f is incident with a 3-face. Otherwise, H contains a subgraph isomorphic to a house. By Lemmas 1 (1) and (2), it is easy to see that m2≤2 and m2+m3≤3. When m2+m3≤2, the number of 4−,4−,5+-faces adjacent to f is at most 6−2m2+m3. Therefore, f has at least min6−4−1−1/2−2×1/6,6−4−1−4×1/6,6−4−6×1/6=1/6 after R5 to (R6), and hence, c′f≥0 by R7. When m2+m3=3, it follows that f is not adjacent to any 4−,4−,5+-faces. Therefore, f has at least 6−4−1−2×1/2=0 after R5 to (R6), and c′f≥0.For the convenience of provingc′v≥0 for every v∈VH, we first introduce the following lemma, which indicates that every 7+-face has positive charges.Lemma 8.
Letv be a 6-vertex. Then, v receives at least 1/8 from each of its incident 7+-face by R7.Proof.
Letf be a k-face incident with v, where k is an integer and k≥7. Clearly, the number of 4−,4−,5+-faces adjacent to f is at most k−2m2+m3.
Supposek≥8. Then, f has at least k−4−m2−1/2×m3−1/6×k−2×m2+m3=5/6k−4−2/3m2−1/6m3 charges after (R5) to (R6) since 0≤m2≤⌈k−1/2⌉ by Lemma 1 (2) and m2+m3≤⌈k/2⌉ by Lemma 1 (1). Therefore, v receives at least 5/6k−4−2/3m2−1/6m3/k−m2−m3=5/6−1/6⋅24−m2−4m3/k−m2−m3≥5/6−1/6×17/4=1/8 when m2=3,m3=1,k=8 from f.
Supposek=7. Clearly, m2+m3≤3. Particularly, in the case of m2+m3=3, f is not adjacent to any 4−,4−,5+-face. First, when m2=3, it has that f is incident with at most two 2-vertices that are incident with a 3-face (otherwise, there is a subgraph isomorphic to a house and a contradiction). Therefore, f has at least 7−4−2−1/2=1/2 charges after (R5) to (R6). Second, when m2=2, it follows that m3≤1. If m3=0, then f is adjacent to at most three 4−,4−,5+-faces (note that when f is adjacent to a 4−,4−,5+-face, f has to be incident with a 4-vertex. So, f is incident with at most four 6-vertices in this case). Therefore, f has at least 7−4−2−3×1/6=1/2 charges after (R5) to (R6). If m3=1, then f is not adjacent to any (4−,4−,5+)-face. Therefore, f has at least 7−4−2−1/2=1/2 charges after (R5) to (R6). Third, when m2≤1, it has that m3≤2. In this case, we can see that f has at least 7−4−1−1/2−1/2=1 charges after (R5) to (R6). All of the above show that f sends v at least 1/4×1/2=1/8 by (R7).
By Lemma8, we can see that c′f≥0 for every 7+-face f.


### 4.1. Final Charge of Vertices

We start with an observation and a lemma.Observation. Let v be a vertex of H. Since H has no subgraph isomorphic to a diamond, we have n3≤⌈dHv−1/2⌉. Moreover, if v is a 6-vertex, then by the condition of Theorem 1, n4≤3 and n3+n4≤3.Lemma 9.
Suppose thatv is a 6-vertex incident with three consecutive faces of size 4, 6, and 4, respectively, where the 6-face is denoted by f, see Figure 3(a). Then, by R7, f gives v at least(1)
1/8 if f is incident with at most two 3−-vertices(2)
1/6 if f is incident with three 3−-vertices and dHv1=dHv2=2 (see Figure 3(b))(3)
1/9 if f is incident with three 3−-vertices and dHv1=dHv2=3 (see Figure 3(c))(4)
2/9 if f is incident with three 3−-vertices and dHv1≠dHv2Figure 3
Cases of Lemma9.
(a)
(b)
(c)
(d)Figure 4
Illustration for the proof of case 2.
(a)
(b)Figure 5
Illustration for the proof of case 3.Proof.
SinceH contains no subgraph isomorphic to a diamond or a house, v1 and v2 are not incident with a 3-face if dHv1≤3 and dHv1≤3, and f is incident with at most one 2-vertex that is incident with a 3-face.
For (1), ifdHv1≤3 and dHv2≤3, then f is adjacent to at most two 4−,4−,5+-faces. Therefore, f has at least 6−4−1/2−1/2−2×1/6=4/6 charges after (R5) to (R6), and v receives at least 1/4×4/6=1/6 from f.
If exact one ofv1 and v2 is a 3−-vertex, say v1, then we consider two cases. First, m2+m3=2. In this case, f is adjacent to at most one 4−,4−,5+-face. Particularly, if v1 is a 2-vertex, denoted by x = NHv1/v, then x is not adjacent to another 2-vertex that is incident with a 3-face by Lemma 3. This implies that when f is incident with a 2-vertex that is incident with a 3-face, the 2-vertex is a neighbor of v2, and so f is not incident with any 4−,4−,5+-face. Consequently, f has at least min{6−4−1/2−1=1/2 (when v1 is a 2-vertex)and 6−4−1/3−1−1/6=1/2 (when v1 is a 3-vertex)} = 1/2 charges after (R5) to (R6), and v receives at least 1/4×1/2=1/8 from f. Second, m2+m3=1, i.e., f is incident with only one 3−-vertex v1. Then, f is adjacent to at most three 4−,4−,5+-faces. Therefore, f has at least 6−4−1/2−3×1/6=1 charges after (R5) to (R6), and v receives at least 1/4 from f.
IfdHv1≥4 and dHv2≥4, then m2+m3≤2. When m2+m3=2, one can readily check that f is not adjacent to any 4−,4−,5+-face. Therefore, f has at least 6−4−1/2−1=1/2 charges after (R5) to (R6), and v receives at least 1/4×1/2=1/8 from f. When m2+m3=1, it has that f is adjacent to at most two 4−,4−,5+-faces. Therefore, f has at least 6−4−1−2×1/6=2/3 charges after (R5) to (R6), and v receives at least 1/5×2/3=2/15 from f. When m2+m3=0, it has that f has at least 6−4−4×1/6=4/3 charges after (R5) to (R6), and v receives more than 1/6×4/3=2/9 from f.
For (2) and (3), it follows thatf is not adjacent to any 4−,4−,5+-face. If dHv1=dHv2=2, then the other 3−-vertex incidents with f are a 3-vertex. Therefore, f has at least 6−4−1/2−1/2−1/2=1/2 charges after (R5) to (R6), and v receives at least 1/2×1/3=1/6 from f. If dHv1=dHv2=3, then f has at least 6−4−1/3−1/3−1=1/3 charges after (R5) to (R6), and v receives at least 1/3×1/3=1/9 from f.
For (4), it is clear thatv1 and v2 are 3−-vertices. Without loss of generality, we assume dHv1=2 and dHv2=3, see Figure 3(d), where v3 is another 3−-vertex incident with f. If dHv3=2, then v3 is not incident with a 3-face by Lemma 3. Therefore, f has at least 6−4−1/2−1/3−1/2=2/3 charges after (R5) to (R6), and v receives at least 1/3×2/3=2/9 from f.
In the following, we turn to the proof ofc′v≥0 for every v∈VH. Let v∈VH be a vertex of H. By Lemma 1 (1), we have dHv≥2.
Suppose thatv is a 2-vertex. Then, v has two neighbors with degree 6 by Lemma 1 (1). If v is incident with a 3-face, then v is incident with a 5+-face. So, v receives 1/2 from each of its neighbors by (R3) and receives 1 from its incident 5+-face. Hence, c′v=2−4+2×1/2+1=0. If v is not incident with a 3-face, then by (R3), v receives 4/5 from its master and 1/5 from its other neighbor of degree 6 and receives 1/2 from each of its adjacent 4+-face by (R4) and (R5). Therefore, c′v=2−4+4/5+1/5+2×1/2=0.
Suppose thatv is a 3-vertex. If v is incident with a 3-face, then v is incident with two 5+-faces since H does not contain any subgraph isomorphic to a house. So, by R5,c′v=3−4+2×1/2=0. If v is not incident with any 3-face, then v is incident with three 4+-faces. Hence, by (R4) and (R5), c′v=−1+3×1/3=0.
Suppose thatv is a 4-vertex. By the discharging rules (R1) to (R7), we have c′v=cv=0.
Suppose thatv is a 5-vertex. By the observation, we have n3≤2. If n3=0, then v is incident with at most five 4-faces. So, by (R1), c′v≥1−5×1/5 = 0. If n3=1, then n4≤2 by the condition of Theorem 1. So, by (R1), c′v≥1−1/2−2×1/5=1/10 = 1/10. If n3 = 2, then n4=0 by the same reason. So, by (R1), c′v≥1−2×1/2 = 0.
Suppose thatdHv=6. By the observation, we have n3+n4≤3. Denote by t2 the number of 2-vertices adjacent to v. Then, t2≤5 by Lemma 6. When t2=0, it is clear that c′v≥6−4−3×1/2=1/2 by (R1) and (R2). When t2=1, denote by u the unique 2-vertex adjacent to v. First, n3+n4≤2. Then, c′v≥6−4−4/5−2×1/2=c′v≥6−4−1/2−3×1/5=0 by (R1), (R2), and (R3). Second, n3+n4=3. In this case, by the condition of Theorem 1, either n3=3 or n4=3. For the former, we have c′v≥6−4−1/2−3×1/2=0 by (R1), (R2), and (R3). For the latter case, if u is incident with a 2,6,3,6-face, then v is incident with at most one (3, 5, 3, 6)-face by Lemma 6. Therefore, c′v≥6−4−4/5−5/12−7/15−1/6=3/20 by (R2) and (R3); if u is not incident with a 2,6,3,6-face, then v is incident with at most two (3, 5, 3, 6)-faces. Therefore, c′v≥6−4−4/5−1/4−7/15−7/15=1/60 by (R2) and (R3). In what follows, we assume t2≥2, and then, by Lemma 3, we have that every 2-vertex is not incident with a 3-face. Thus, when n3+n4=0, c′v≥6−4−4/5−4×1/5=2/5 by (R3). Now, we further consider the following three cases:Case 1. n3+n4=1. If n3=1 and n4=0, then t2≤4 by Lemma 3. Therefore, c′v≥6−4−4/5−3×1/5−1/2=1/10 by (R1) and (R3). If n3=0 and n4=1, denoted by f the 4-face incident with v, then by Lemma 6 and (R2) and (R3), when f is a (2, 6, 3, 6)-face, it has that t2≤4 and c′v≥6−4−4/5−3×1/5−5/12=11/60; when f is a 2,6,4+,6-face, t2≤5 and c′v≥6−4−4/5−4×1/5−1/4=3/20; when f is a 3,5+,3,5+-face, t2≤3 and c′v≥6−4−4/5−2×1/5−7/15=1/3; when f is a 3,5+,4+,5+-face, t2≤4 and c′v≥6−4−4/5−3×1/5−1/6=13/30; and when f is a 4+,4+,4+,4+-face, t2≤4 and c′v≥6−4−4/5−3×1/5=3/5.Case 2. n3+n4=2. If t2=2, then c′v≥6−4−4/5−1/5−1/2−1/2=0 by (R1), (R2), and (R3). If t2≥3, then we have n3≤1 by Lemma 3 and the assumption that H contains no subgraph isomorphic to a diamond. In the following, we consider two subcases:Case 2.1. n3=0andn4=2. Let NHv=v1,v2,v3,v4,v5,v6 and f1 and f2 be the two 4-faces incident with v, see Figure 4(a). By Lemma 2, each of f1 and f2 is incident with at most one 2-vertex, so t2≤4.Whent2=3, it has that at least one of f1, and f2 is incident with a 2-vertex, say f1. By Lemma 1 (1), it follows that f1 is a (2, 6, 3+, 6)-face. If f1 is a (2, 6, 4+, 6)-face, then c′v≥6−4−4/5−2×1/5−1/4−7/15=1/12 by (R2) and (R3). If f1 is a (2, 6, 3, 6)-face, then we further consider the following two cases regarding to f2. First, f2 is incident with a 2-vertex, i.e., f2 is a (2, 6, 3+, 6)-face by Lemma 1 (1). If f2 is a (2, 6, 4+, 6)-face, then c′v≥6−4−4/5−2×1/5−1/4−5/12=2/15 by (R2) and (R3). Otherwise, f2 is a (2, 6, 3, 6)-face. In this case, according to Lemmas 7 (1) and (2), we can deduce that f is a 6+-face. Therefore, according to Lemmas 8 and 9, v receives at least 1/8 from f by (R7). So, c′v≥6−4−4/5−2×1/5−2×5/12+1/8=11/120 by (R2), (R3), and (R7). Second, f2 is not incident with any 2-vertex. Then, we consider m3f2, the number of 3-vertices incident with f2. Obviously, m3f2≤1 by Lemma 1 (1) and Lemma 6 (since t2 = 3). Hence, c′v≥6−4−4/5−2×1/5−5/12−1/6=13/60 by (R2) and (R3).Whent2=4, it follows that both f1 and f2 are 2,6,3+,6-faces by Lemma 1 (1) and Lemma 2, and at most one of them is a 2,6,3,6-face by Lemma 6. Naturally, v4 and v5 are 2-vertex, and neither of them is incident with a 3-face. Denote by f the face incident with v,v1, and v2, see Figure 4(a). Then, dHf′=6 by Lemma 7 (1). If dHf′=6, then by (R7), it sends at least min1/3×6−4−2×1/2−1/2,1/4×6−4−2×1/2=1/6 to v. If dHf′≥7, then it sends at least 1/8 to v by Lemma 8. Therefore, c′v≥6−4−4/5−3×1/5−5/12−1/4+1/8=7/120 by (R2) and (R3).Case 2.2. n3=1,andn4=1. Denote by f1 and f2 the 3-face and 4-face incident with v and f′ the face incident with v and not adjacent to f1 or f2, see Figure 4(b). By Lemmas 2 and 3, we can see that f1 is not incident with any 2-vertex (since t2≥3), f2 is incident with one 2-vertex, and v4andv5 are 2-vertices. Obviously, v4 and v5 are not incident with any 3-face. Additionally, by Lemma 7 (1), we can see that dHf′≥6. Thus, with an analogous proof as above (Case 2.1), v can receive at least 1/8 from f′ by (R7). Therefore, c′v≥6−4−4/5−2×1/5−1/2−5/12+1/8=1/120 by (R2) and (R3).Case 3. n3+n4=3. In this case, since we assume t2≥2, it has that n3=0 and n4=3 by the condition of Theorem 1 and Lemma 3. Denote by f1,f2,andf3 the three 4-faces incident with v and f1′,f2′,andf3′ the three 5+-faces incident with v, see Figure 5. By Lemma 2, it has that t2≤3.Case 3.1. t2=2. Without loss of generality, we assume f1 and f2 are incident with 2-vertices. Then, both of f1 and f2 are 2,6,3+,6-faces by Lemma 1 (1). Now, we turn to considering f3. First, f3 is incident with two 3-vertices, i.e., both v1 and v2 are 3-vertices. Then, at most one of f1 and f2 is a (2, 6, 3, 6)-face. If both f1 and f2 are (2, 6, 4+, 6)-face, then c′v≥6−4−4/5−1/5−7/15−1/4−1/4=1/30 by (R2) and (R3). Otherwise, we assume f1 is a (2, 6, 3, 6)-face. In this case, by (R7), when dHv5=3, according to Lemmas 8 and 9, v can receive at least 1/3×5−4−1/3−1/2=1/18 from fi′ for i=1,2,3 if fi′ is a 5-face; when dHv5=2, we have that dHv6=3, and v can receive at least 1/3×5−4−1/3−1/3=1/9 from f1′ if f1′ is a 5-face and at least 1/3×5−4−1/3−1/2=1/18 from f3′ if f3′ is a 5-face. Additionally, by Lemmas 8 and 9, v can receive at least 1/9 from fi′ for i=1,2,3 if fi′ is a 6+-face. Therefore, c′v≥6−4−4/5−1/5−7/15−5/12−1/4+3×1/18=1/30 by (R2) and (R3). Second, f3 is incident with at most one 3-vertices. Then, c′v≥6−4−4/5−1/5−1/6−5/12−5/12=0 by (R2) and (R3).Case 3.2. t2=3. Then, each of fi is a (2, 6, 3+, 6)-face, where i∈1,2,3. Particularly, by Lemma 6, at most two of them are (2, 6, 3, 6)-faces. When v is incident with at most one (2, 6, 3, 6)-face, we, without loss of generality, assume that f3 is a (2, 6, 3, 6)-face, and by symmetry, let dHv1=3 and dHv2=2. If v6 (or v3) is a 2-vertex, then by Lemma 7 (2) (or Lemma 7 (1)), f1′ (or f3′) is a 6+-face. If neither v6 nor v3 is a 2-vertex, then v4 and v5 are 2-vertices, and by Lemma 7 (1), f2′ is a 6+-face. Therefore, by Lemmas 8 and 9, v can receive at least 1/8 from fi′ for some i∈1,2,3 by (R7) (note that v is adjacent to at most one 3-vertex in this case). Hence, c′v≥6−4−4/5−2×1/5−1/4−5/12−1/4+1/8=1/120 by (R2) and (R3). When v is incident with two (2, 6, 3, 6)-faces, by symmetry, we assume f1 and f2 are (2, 6, 3, 6)-faces. Without loss of generality, we assume dHv1=2 and then dHv2≥4.
First, ifdHv5=3 and dHv5=3, then f1′ is a 6+-face by Lemma 7 (1). When f1′ is a 6-face, f1′ gives v at least 1/3×6−4−1/2−1/2−1/2=1/6; when f1′ is a k-face, where k≥7, by R2,R3, and R7, we can deduce that f1′ gives v at least k−4−2×1/2−m2f1′−2−1/2×m3f1′−1/6×k−2m2f1′−2m3f1′/k−m2f1′−m3f1′≥5/24k=7,m2f1′=3,m3f1′=0.
Consider the facef2′. If f2′ is a 6+-face, then by R7,f2′ sends at least 1/9 to v according to Lemmas 8 and 9. If f2′ is a 5-face, then by Lemmas 7 (1) and (2), we can deduce that dHv4=3. So, f2′ sends at least 1/3×5−4−1/3−1/3=1/9 to v by (R7).
Consider the facef3′. If f3′ is a 6+-face, then by R7,f3′ sends at least 1/8 to v according to Lemmas 8 and 9. If f3′ is a 5-face, then when dHv3=3, f3′ sends at least 1/3×5−4−1/3−1/2=1/18 to v; when dHv3=2, let v2,v,v3,u1,u2 be the five vertices incident with f3′, where u1 is adjacent to v3 and u2 is adjacent to v2. Then, dHu1=6 by Lemma 1 (1), and dHu2≥3 by Lemma 7 (3). If dHu2≥4, then v can receive at least 1/3×5−4−1/2−2×1/6=1/18 from f3′. Otherwise, if dHu2=3, then dHv2≥5, and f3 is incident with only one 3−-vertex v1. So, f3 has at least 2×1/4+1/5−1/2=1/5 after (R1), (R2), and (R4). So, f3 gives v at least 1/15 by (R7) in this case.
To sum up, we havec′v≥6−4−4/5−2×1/5−1/4−5/12−5/12+1/6+1/9+1/18=1/20 by (R2) and (R3).
Second, ifdHv6=3 and dHv5=2, then both f1′ and f2′ are 6+-faces by Lemmas 7 (1) and (2). So, each of f1′ and f2′gives v at least 1/8 by Lemmas 8 and 9. In addition, with the similar analysis as the above, v can receive at least either 1/18 from f3′ or 1/15 from f3. Hence, c′v≥6−4−4/5−2×1/5−1/4−5/12−5/12+1/8+1/8+1/18=1/45 by (R2) and (R3).
In all cases, we have shown thatc′x≥0 for every x∈VH∪FH. Therefore, ∑x∈VH∪FHcx=∑x∈VH∪FHc′x≥0, a contradiction. This completes the proof of Theorem 1.


## 4.1. Final Charge of Vertices

We start with an observation and a lemma.Observation. Let v be a vertex of H. Since H has no subgraph isomorphic to a diamond, we have n3≤⌈dHv−1/2⌉. Moreover, if v is a 6-vertex, then by the condition of Theorem 1, n4≤3 and n3+n4≤3.Lemma 9.
Suppose thatv is a 6-vertex incident with three consecutive faces of size 4, 6, and 4, respectively, where the 6-face is denoted by f, see Figure 3(a). Then, by R7, f gives v at least(1)
1/8 if f is incident with at most two 3−-vertices(2)
1/6 if f is incident with three 3−-vertices and dHv1=dHv2=2 (see Figure 3(b))(3)
1/9 if f is incident with three 3−-vertices and dHv1=dHv2=3 (see Figure 3(c))(4)
2/9 if f is incident with three 3−-vertices and dHv1≠dHv2Figure 3
Cases of Lemma9.
(a)
(b)
(c)
(d)Figure 4
Illustration for the proof of case 2.
(a)
(b)Figure 5
Illustration for the proof of case 3.Proof.
SinceH contains no subgraph isomorphic to a diamond or a house, v1 and v2 are not incident with a 3-face if dHv1≤3 and dHv1≤3, and f is incident with at most one 2-vertex that is incident with a 3-face.
For (1), ifdHv1≤3 and dHv2≤3, then f is adjacent to at most two 4−,4−,5+-faces. Therefore, f has at least 6−4−1/2−1/2−2×1/6=4/6 charges after (R5) to (R6), and v receives at least 1/4×4/6=1/6 from f.
If exact one ofv1 and v2 is a 3−-vertex, say v1, then we consider two cases. First, m2+m3=2. In this case, f is adjacent to at most one 4−,4−,5+-face. Particularly, if v1 is a 2-vertex, denoted by x = NHv1/v, then x is not adjacent to another 2-vertex that is incident with a 3-face by Lemma 3. This implies that when f is incident with a 2-vertex that is incident with a 3-face, the 2-vertex is a neighbor of v2, and so f is not incident with any 4−,4−,5+-face. Consequently, f has at least min{6−4−1/2−1=1/2 (when v1 is a 2-vertex)and 6−4−1/3−1−1/6=1/2 (when v1 is a 3-vertex)} = 1/2 charges after (R5) to (R6), and v receives at least 1/4×1/2=1/8 from f. Second, m2+m3=1, i.e., f is incident with only one 3−-vertex v1. Then, f is adjacent to at most three 4−,4−,5+-faces. Therefore, f has at least 6−4−1/2−3×1/6=1 charges after (R5) to (R6), and v receives at least 1/4 from f.
IfdHv1≥4 and dHv2≥4, then m2+m3≤2. When m2+m3=2, one can readily check that f is not adjacent to any 4−,4−,5+-face. Therefore, f has at least 6−4−1/2−1=1/2 charges after (R5) to (R6), and v receives at least 1/4×1/2=1/8 from f. When m2+m3=1, it has that f is adjacent to at most two 4−,4−,5+-faces. Therefore, f has at least 6−4−1−2×1/6=2/3 charges after (R5) to (R6), and v receives at least 1/5×2/3=2/15 from f. When m2+m3=0, it has that f has at least 6−4−4×1/6=4/3 charges after (R5) to (R6), and v receives more than 1/6×4/3=2/9 from f.
For (2) and (3), it follows thatf is not adjacent to any 4−,4−,5+-face. If dHv1=dHv2=2, then the other 3−-vertex incidents with f are a 3-vertex. Therefore, f has at least 6−4−1/2−1/2−1/2=1/2 charges after (R5) to (R6), and v receives at least 1/2×1/3=1/6 from f. If dHv1=dHv2=3, then f has at least 6−4−1/3−1/3−1=1/3 charges after (R5) to (R6), and v receives at least 1/3×1/3=1/9 from f.
For (4), it is clear thatv1 and v2 are 3−-vertices. Without loss of generality, we assume dHv1=2 and dHv2=3, see Figure 3(d), where v3 is another 3−-vertex incident with f. If dHv3=2, then v3 is not incident with a 3-face by Lemma 3. Therefore, f has at least 6−4−1/2−1/3−1/2=2/3 charges after (R5) to (R6), and v receives at least 1/3×2/3=2/9 from f.
In the following, we turn to the proof ofc′v≥0 for every v∈VH. Let v∈VH be a vertex of H. By Lemma 1 (1), we have dHv≥2.
Suppose thatv is a 2-vertex. Then, v has two neighbors with degree 6 by Lemma 1 (1). If v is incident with a 3-face, then v is incident with a 5+-face. So, v receives 1/2 from each of its neighbors by (R3) and receives 1 from its incident 5+-face. Hence, c′v=2−4+2×1/2+1=0. If v is not incident with a 3-face, then by (R3), v receives 4/5 from its master and 1/5 from its other neighbor of degree 6 and receives 1/2 from each of its adjacent 4+-face by (R4) and (R5). Therefore, c′v=2−4+4/5+1/5+2×1/2=0.
Suppose thatv is a 3-vertex. If v is incident with a 3-face, then v is incident with two 5+-faces since H does not contain any subgraph isomorphic to a house. So, by R5,c′v=3−4+2×1/2=0. If v is not incident with any 3-face, then v is incident with three 4+-faces. Hence, by (R4) and (R5), c′v=−1+3×1/3=0.
Suppose thatv is a 4-vertex. By the discharging rules (R1) to (R7), we have c′v=cv=0.
Suppose thatv is a 5-vertex. By the observation, we have n3≤2. If n3=0, then v is incident with at most five 4-faces. So, by (R1), c′v≥1−5×1/5 = 0. If n3=1, then n4≤2 by the condition of Theorem 1. So, by (R1), c′v≥1−1/2−2×1/5=1/10 = 1/10. If n3 = 2, then n4=0 by the same reason. So, by (R1), c′v≥1−2×1/2 = 0.
Suppose thatdHv=6. By the observation, we have n3+n4≤3. Denote by t2 the number of 2-vertices adjacent to v. Then, t2≤5 by Lemma 6. When t2=0, it is clear that c′v≥6−4−3×1/2=1/2 by (R1) and (R2). When t2=1, denote by u the unique 2-vertex adjacent to v. First, n3+n4≤2. Then, c′v≥6−4−4/5−2×1/2=c′v≥6−4−1/2−3×1/5=0 by (R1), (R2), and (R3). Second, n3+n4=3. In this case, by the condition of Theorem 1, either n3=3 or n4=3. For the former, we have c′v≥6−4−1/2−3×1/2=0 by (R1), (R2), and (R3). For the latter case, if u is incident with a 2,6,3,6-face, then v is incident with at most one (3, 5, 3, 6)-face by Lemma 6. Therefore, c′v≥6−4−4/5−5/12−7/15−1/6=3/20 by (R2) and (R3); if u is not incident with a 2,6,3,6-face, then v is incident with at most two (3, 5, 3, 6)-faces. Therefore, c′v≥6−4−4/5−1/4−7/15−7/15=1/60 by (R2) and (R3). In what follows, we assume t2≥2, and then, by Lemma 3, we have that every 2-vertex is not incident with a 3-face. Thus, when n3+n4=0, c′v≥6−4−4/5−4×1/5=2/5 by (R3). Now, we further consider the following three cases:Case 1. n3+n4=1. If n3=1 and n4=0, then t2≤4 by Lemma 3. Therefore, c′v≥6−4−4/5−3×1/5−1/2=1/10 by (R1) and (R3). If n3=0 and n4=1, denoted by f the 4-face incident with v, then by Lemma 6 and (R2) and (R3), when f is a (2, 6, 3, 6)-face, it has that t2≤4 and c′v≥6−4−4/5−3×1/5−5/12=11/60; when f is a 2,6,4+,6-face, t2≤5 and c′v≥6−4−4/5−4×1/5−1/4=3/20; when f is a 3,5+,3,5+-face, t2≤3 and c′v≥6−4−4/5−2×1/5−7/15=1/3; when f is a 3,5+,4+,5+-face, t2≤4 and c′v≥6−4−4/5−3×1/5−1/6=13/30; and when f is a 4+,4+,4+,4+-face, t2≤4 and c′v≥6−4−4/5−3×1/5=3/5.Case 2. n3+n4=2. If t2=2, then c′v≥6−4−4/5−1/5−1/2−1/2=0 by (R1), (R2), and (R3). If t2≥3, then we have n3≤1 by Lemma 3 and the assumption that H contains no subgraph isomorphic to a diamond. In the following, we consider two subcases:Case 2.1. n3=0andn4=2. Let NHv=v1,v2,v3,v4,v5,v6 and f1 and f2 be the two 4-faces incident with v, see Figure 4(a). By Lemma 2, each of f1 and f2 is incident with at most one 2-vertex, so t2≤4.Whent2=3, it has that at least one of f1, and f2 is incident with a 2-vertex, say f1. By Lemma 1 (1), it follows that f1 is a (2, 6, 3+, 6)-face. If f1 is a (2, 6, 4+, 6)-face, then c′v≥6−4−4/5−2×1/5−1/4−7/15=1/12 by (R2) and (R3). If f1 is a (2, 6, 3, 6)-face, then we further consider the following two cases regarding to f2. First, f2 is incident with a 2-vertex, i.e., f2 is a (2, 6, 3+, 6)-face by Lemma 1 (1). If f2 is a (2, 6, 4+, 6)-face, then c′v≥6−4−4/5−2×1/5−1/4−5/12=2/15 by (R2) and (R3). Otherwise, f2 is a (2, 6, 3, 6)-face. In this case, according to Lemmas 7 (1) and (2), we can deduce that f is a 6+-face. Therefore, according to Lemmas 8 and 9, v receives at least 1/8 from f by (R7). So, c′v≥6−4−4/5−2×1/5−2×5/12+1/8=11/120 by (R2), (R3), and (R7). Second, f2 is not incident with any 2-vertex. Then, we consider m3f2, the number of 3-vertices incident with f2. Obviously, m3f2≤1 by Lemma 1 (1) and Lemma 6 (since t2 = 3). Hence, c′v≥6−4−4/5−2×1/5−5/12−1/6=13/60 by (R2) and (R3).Whent2=4, it follows that both f1 and f2 are 2,6,3+,6-faces by Lemma 1 (1) and Lemma 2, and at most one of them is a 2,6,3,6-face by Lemma 6. Naturally, v4 and v5 are 2-vertex, and neither of them is incident with a 3-face. Denote by f the face incident with v,v1, and v2, see Figure 4(a). Then, dHf′=6 by Lemma 7 (1). If dHf′=6, then by (R7), it sends at least min1/3×6−4−2×1/2−1/2,1/4×6−4−2×1/2=1/6 to v. If dHf′≥7, then it sends at least 1/8 to v by Lemma 8. Therefore, c′v≥6−4−4/5−3×1/5−5/12−1/4+1/8=7/120 by (R2) and (R3).Case 2.2. n3=1,andn4=1. Denote by f1 and f2 the 3-face and 4-face incident with v and f′ the face incident with v and not adjacent to f1 or f2, see Figure 4(b). By Lemmas 2 and 3, we can see that f1 is not incident with any 2-vertex (since t2≥3), f2 is incident with one 2-vertex, and v4andv5 are 2-vertices. Obviously, v4 and v5 are not incident with any 3-face. Additionally, by Lemma 7 (1), we can see that dHf′≥6. Thus, with an analogous proof as above (Case 2.1), v can receive at least 1/8 from f′ by (R7). Therefore, c′v≥6−4−4/5−2×1/5−1/2−5/12+1/8=1/120 by (R2) and (R3).Case 3. n3+n4=3. In this case, since we assume t2≥2, it has that n3=0 and n4=3 by the condition of Theorem 1 and Lemma 3. Denote by f1,f2,andf3 the three 4-faces incident with v and f1′,f2′,andf3′ the three 5+-faces incident with v, see Figure 5. By Lemma 2, it has that t2≤3.Case 3.1. t2=2. Without loss of generality, we assume f1 and f2 are incident with 2-vertices. Then, both of f1 and f2 are 2,6,3+,6-faces by Lemma 1 (1). Now, we turn to considering f3. First, f3 is incident with two 3-vertices, i.e., both v1 and v2 are 3-vertices. Then, at most one of f1 and f2 is a (2, 6, 3, 6)-face. If both f1 and f2 are (2, 6, 4+, 6)-face, then c′v≥6−4−4/5−1/5−7/15−1/4−1/4=1/30 by (R2) and (R3). Otherwise, we assume f1 is a (2, 6, 3, 6)-face. In this case, by (R7), when dHv5=3, according to Lemmas 8 and 9, v can receive at least 1/3×5−4−1/3−1/2=1/18 from fi′ for i=1,2,3 if fi′ is a 5-face; when dHv5=2, we have that dHv6=3, and v can receive at least 1/3×5−4−1/3−1/3=1/9 from f1′ if f1′ is a 5-face and at least 1/3×5−4−1/3−1/2=1/18 from f3′ if f3′ is a 5-face. Additionally, by Lemmas 8 and 9, v can receive at least 1/9 from fi′ for i=1,2,3 if fi′ is a 6+-face. Therefore, c′v≥6−4−4/5−1/5−7/15−5/12−1/4+3×1/18=1/30 by (R2) and (R3). Second, f3 is incident with at most one 3-vertices. Then, c′v≥6−4−4/5−1/5−1/6−5/12−5/12=0 by (R2) and (R3).Case 3.2. t2=3. Then, each of fi is a (2, 6, 3+, 6)-face, where i∈1,2,3. Particularly, by Lemma 6, at most two of them are (2, 6, 3, 6)-faces. When v is incident with at most one (2, 6, 3, 6)-face, we, without loss of generality, assume that f3 is a (2, 6, 3, 6)-face, and by symmetry, let dHv1=3 and dHv2=2. If v6 (or v3) is a 2-vertex, then by Lemma 7 (2) (or Lemma 7 (1)), f1′ (or f3′) is a 6+-face. If neither v6 nor v3 is a 2-vertex, then v4 and v5 are 2-vertices, and by Lemma 7 (1), f2′ is a 6+-face. Therefore, by Lemmas 8 and 9, v can receive at least 1/8 from fi′ for some i∈1,2,3 by (R7) (note that v is adjacent to at most one 3-vertex in this case). Hence, c′v≥6−4−4/5−2×1/5−1/4−5/12−1/4+1/8=1/120 by (R2) and (R3). When v is incident with two (2, 6, 3, 6)-faces, by symmetry, we assume f1 and f2 are (2, 6, 3, 6)-faces. Without loss of generality, we assume dHv1=2 and then dHv2≥4.
First, ifdHv5=3 and dHv5=3, then f1′ is a 6+-face by Lemma 7 (1). When f1′ is a 6-face, f1′ gives v at least 1/3×6−4−1/2−1/2−1/2=1/6; when f1′ is a k-face, where k≥7, by R2,R3, and R7, we can deduce that f1′ gives v at least k−4−2×1/2−m2f1′−2−1/2×m3f1′−1/6×k−2m2f1′−2m3f1′/k−m2f1′−m3f1′≥5/24k=7,m2f1′=3,m3f1′=0.
Consider the facef2′. If f2′ is a 6+-face, then by R7,f2′ sends at least 1/9 to v according to Lemmas 8 and 9. If f2′ is a 5-face, then by Lemmas 7 (1) and (2), we can deduce that dHv4=3. So, f2′ sends at least 1/3×5−4−1/3−1/3=1/9 to v by (R7).
Consider the facef3′. If f3′ is a 6+-face, then by R7,f3′ sends at least 1/8 to v according to Lemmas 8 and 9. If f3′ is a 5-face, then when dHv3=3, f3′ sends at least 1/3×5−4−1/3−1/2=1/18 to v; when dHv3=2, let v2,v,v3,u1,u2 be the five vertices incident with f3′, where u1 is adjacent to v3 and u2 is adjacent to v2. Then, dHu1=6 by Lemma 1 (1), and dHu2≥3 by Lemma 7 (3). If dHu2≥4, then v can receive at least 1/3×5−4−1/2−2×1/6=1/18 from f3′. Otherwise, if dHu2=3, then dHv2≥5, and f3 is incident with only one 3−-vertex v1. So, f3 has at least 2×1/4+1/5−1/2=1/5 after (R1), (R2), and (R4). So, f3 gives v at least 1/15 by (R7) in this case.
To sum up, we havec′v≥6−4−4/5−2×1/5−1/4−5/12−5/12+1/6+1/9+1/18=1/20 by (R2) and (R3).
Second, ifdHv6=3 and dHv5=2, then both f1′ and f2′ are 6+-faces by Lemmas 7 (1) and (2). So, each of f1′ and f2′gives v at least 1/8 by Lemmas 8 and 9. In addition, with the similar analysis as the above, v can receive at least either 1/18 from f3′ or 1/15 from f3. Hence, c′v≥6−4−4/5−2×1/5−1/4−5/12−5/12+1/8+1/8+1/18=1/45 by (R2) and (R3).
In all cases, we have shown thatc′x≥0 for every x∈VH∪FH. Therefore, ∑x∈VH∪FHcx=∑x∈VH∪FHc′x≥0, a contradiction. This completes the proof of Theorem 1.


## 5. Conclusion

By using the “discharging” approach, we obtain a sufficient condition for a planar graph of maximum degree 6 to be totally 7-colorable. Since no planar graphs of maximum degree 6 that are not totally 7-colorable are found, it is widely believed that every planar graph of maximum degree 6 has a total 7-coloring [11]. Our result enhances the reliability of this conjecture. Nevertheless, to prove TCC for planar graphs, it still requires persistent efforts on the study of structures of planar graphs of maximum degree 6. As a future work, we would like to further explore the structural properties of this kind of graphs, as well as the possibility of applying them in the proof of TCC for planar graphs.



---

*Source: 3196540-2020-04-11.xml*