Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable

Abstract

Let $c_{1},c_{2},\ldots ,c_{k}$ be k non-negative integers. A graph G is $(c_{1},c_{2},\ldots ,c_{k})$-colorable if the vertex set can be partitioned into k sets $V_{1},V_{2},\ldots ,V_{k}$ such that for every $i,1\le i\le k$, the subgraph $G[V_{i}]$ has maximum degree at most $c_{i}$. Steinberg (Ann Discret Math 55:211–248, 1993) conjectured that every planar graph without 4- and 5-cycles is 3-colorable. Xu and Wang (Sci Math 43:15–24, 2013) conjectured that every planar graph without 4- and 6-cycles is 3-colorable. In this paper, we prove that every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable, which improves the result of Xu and Wang (Sci Math 43:15–24, 2013), who proved that every planar graph without 4- and 6-cycles is (1, 1, 0)-colorable.

1 Introduction

All graphs considered in this paper are finite simple graphs. For a planar graph G, we use V, E, and $\delta$ to denote its vertex set, edge set and minimum degree, respectively. For $u\in V(G)$, let N(u) denote the neighbors of u in G. A k-${ vertex}$ (resp. $k^{+}$-${ vertex}$, $k^{-}$- ${ vertex}$) is a vertex of degree k (resp. at least k, at most k). The same notation will be used for faces.

It is well-known that the problem of deciding whether a planar graph is properly 3-colorable is NP-complete. In 1959, Grötzsch (1959) showed the famous theorem that every triangle-free planar graph is 3-colorable. In 1976, Steinberg raised the following famous conjecture.

Conjecture 1.1

[Steinberg (1993)] Every planar graph without 4- and 5-cycles is 3-colorable.

This conjecture was disproved by Cohen–Addad et al. (2016) recently. However, Erdös suggested to find a constant c such that a planar graph without cycles of length from 4 to c is 3-colorable. Abbott and Zhou (1991) proved that such a c exists and $c\le 11$. This bound was improved to $c\le 9$ by Borodin (1996) and independently by Sanders and Zhao (1995), to $c\le 7$ by Borodin et al. (2005). Up to now, it is unknown whether the bound can be decreased to 6.

Another relaxation of the conjecture is to allow some defects in the color classes. Let $c_{1},c_{2},\ldots ,c_{k}$ be k non-negative integers. A graph G is $(c_{1},c_{2},\ldots ,c_{k})$-colorable if the vertex set can be partitioned into k sets $V_{1},V_{2},\ldots ,V_{k}$ such that for every $i,1\le i\le k$, the subgraph $G[V_{i}]$ has maximum degree at most $c_{i}$. Thus, a graph is properly 3-colorable if and only if it is (0,0,0)-colorable. Chang et al. (2011) showed that every planar graph without 4- and 5-cycles is (4, 0, 0)-colorable and (2, 1, 0)-colorable. Improving the result of Chang et al., it is proved that every planar graph without cycles of length 4 or 5 is (3, 0, 0)-colorable (Hill et al. 2013) and (1, 1, 0)-colorable (Hill and Yu 2013; Xu et al. 2014). As a variation, Xu and Wang (2013) conjectured that every planar graph without 4- and 6-cycles is 3-colorable and they proved that every planar graph without 4- and 6-cycles is (3, 0, 0)- and (1, 1, 0)-colorable.

On the other hand, Lih et al. (2001) proved that every planar graph without 4- and 6-cycles is (1, 1, 1)-choosable. As an improvement, Chen et al. (2015) proved that every planar graph without adjacent triangles or 6-cycles is (1, 1, 1)-choosable, where two cycles are adjacent if they have an edge in common. Motivated by those results, we prove the following result.

Theorem 1.2

Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable.

An m-face $f=[u_{1}u_{2}\ldots u_{m}]$ is called an $(a_{1},a_{2},\ldots ,a_{m})$-face if $d(u_{i})=a_{i}$ for $i=1,2,\ldots ,m$. We use $m_{i}(u)$ to denote the number of i-faces incident with u. If a vertex u is incident with a face f, then its neighbor not incident with this face is called its outer neighbor. A 5-vertex u is bad if u is incident with a 3-face, a (5, 3, 3, 4, 3)-face and a $(5, 3,3,5^+,3)$-face, and good otherwise. A neighbor $v'$ of a vertex v is isolated if no 3-face in G contains $vv'$.

Like many similar results, we use a discharging procedure to prove Theorem 1.2. We show some reducible configurations in the next section, and then in the last section, use discharging argument to reach a contradiction.

2 Reducible configurations of G

Let G be a counterexample to Theorem 1.2 with minimizing $|V(G)|+|E(G)|$. Thus, G is connected. Embed G into the plane, we get a plane graph $G=(V, E, F)$, where F is the set of faces of G. Since G has no 6-cycles and no adjacent 3- and 4-cycles, we have the following

Lemma 2.1

No two $4^-$-faces are adjacent, and no 3-face is adjacent to a 5-face in G.

Lemma 2.2

[Xu et al. (2014)] The following are some properties of G:

• (1) $\delta (G)\ge 3$.

• (2) Every 3-vertex is adjacent to at most one 3-vertex.

• (3) A 4-vertex has at least one $4^{+}$-neighbor.

• (4) There is no $(3,3,4^-)$-face in G.

• (5) If a 3-vertex u is incident with a (3, 4, 4)-face, then the outer neighbor of u is a $4^{+}$-vertex.

• (6) If a 4-vertex is incident with exactly one 3-face that is a (3, 4, 4)-face, then it is adjacent to an isolated $4^+$-vertex.

• (7) If a 4-vertex is incident with two 3-faces one of which is a (3, 4, 4)-face, then it is adjacent to at least one $5^+$-vertex.

Lemma 2.3

There is no (4, 3, 3, 4, 3)-face in G.

Proof

Suppose to the contrary that $f=[u_{1}u_{2}u_{3}u_{4}u_{5}]$ is a (4, 3, 3, 4, 3)-face. By the minimality of G, we can first color $G-\{u_i: 1\le i\le 5\}$. Color $u_1$ and $u_4$ properly. Assume first that $u_1$ is not colored 3. Let $u_5'$ be the outer neighbor of $u_5$. If the colors of $u_1, u_4$ and $u_5'$ are different, then color $u_5$ with the same color of $u_1$ since $u_1$ was colored 1 or 2. If at least two of $u_1$, $u_4$ and $u_5'$ are colored the same color, then $u_5$ can be properly colored. Now we properly color $u_2$. Let $u_3'$ be the outer neighbor of $u_3$. If at least two of $u_2, u_4$ and $u_3'$ are colored the same color, then $u_3$ can be properly colored. If the colors of $u_2, u_4$ and $u_3'$ are different, then color $u_3$ with 1 or 2 since at least one of $u_2$ and $u_4$ is not colored with 3 (say $u_2$ and color $u_3$ with color of $u_2$), a contradiction. Thus, by symmetry, we assume that both $u_1$ and $u_4$ are colored 3. In this case, properly color $u_5$ and $u_2$. The vertex $u_3$ can be either properly colored or colored with the color of $u_2$, a contradiction. $\square$

Lemma 2.4

Let u be a 5-vertex in G.

• (a) The vertex u is incident with at most four $(5, 3, 3, 4^+, 3)$-faces.

• (b) The vertex u is incident with at most one (5, 3, 3, 4, 3)-faces.

• (c) If u is incident with a (5, 3, 3, 4, 3)-face, then it is incident with at most two $(5, 3, 3, 5^+,3)$-faces.

Proof

(a) Suppose to the contrary that u is incident with five $(5, 3, 3, 4^+, 3)$-faces $f_1=[uu_1u_2u_3u_4]$, $f_2=[uu_4u_5u_6u_7], f_3=[uu_7u_8u_9u_{10}], f_4=[uu_{10}u_{11}u_{12}u_{13}]$ and $f_5=[uu_{13}u_{14}u_{15}u_1]$. Then $u_1u_2\ldots u_{15}$ is a 15-cycle and $u_1, u_4, u_7, u_{10}, u_{13}$ are neighbors of u. Then the neighbors of u are all 3-vertices, and moreover, each of them must be adjacent to a 3-vertex and a $4^+$-vertex, as no 3-vertex is adjacent to two 3-vertices on the cycle by Lemma 2.2 (2). We assume, without loss of generality, that each of $u_3, u_6, u_9, u_{12}$ and $u_{15}$ is a $4^+$-vertex.

By the minimality of G, $G-N[u]$ can be colored. Since each of $u_2, u_5, u_8, u_{11}$ and $u_{14}$ has only two colored neighbors in $G-N[u]$, we can further assume that each of $u_2, u_5, u_8, u_{11}$ and $u_{14}$ can be recolored (if necessary) so that they are properly colored. Note that each of $u_1, u_4, u_7, u_{10}$ and $u_{13}$ has only two colored neighbors, one of which is properly colored. Observe two colored neighbors $u_2$ and $u_{15}$ of $u_1$. If at least one of $u_1$ and $u_{15}$ is colored with 3, we can properly color $u_1$ with 1 or 2. Thus, assume that none of $u_2$ and $u_{15}$ is colored with 3. If $u_2$ and $u_{15}$ are colored with different colors, then we color $u_1$ with the color of $u_2$; if $u_2$ and $u_{15}$ are colored with the same color, we color $u_1$ with the color which is neither 3 nor the color used by $u_2$ and $u_{15}$. This means that we may also color $u_1$ so that 3 is not used. Similarly, we color each of $u_4, u_7, u_{10}$ and $u_{13}$ so that 3 is not used. Finally, u can be colored with 3, a contradiction since G is not (1, 1, 0)-colorable.

(b) Suppose to the contrary that u is incident with two (5, 3, 3, 4, 3)-faces. Then the two 5-faces may or may not have a common edge. So we consider two cases.

Case (b.1): The two 5-faces share an common edge. Let $[uu_1u_2u_3u_4]$ and $[u_4u_5u_6u_7u]$ be the two 5-faces, and v, w be the other two neighbors of u. It follows that $u_1, u_4, u_7$ are 3-neighbors of u. By the minimality of G, $G-\{u, u_i: 1\le i\le 7\}$ can be colored, and furthermore, as each of $u_i$, $1\le i\le 7$, has at most two colored neighbors, we may properly color them. Now we try to color u.

Note that each of $u_1$ and $u_7$ has at least one properly colored neighbor, we may recolor them so that 3 is not used, and $u_4$ has two properly colored neighbors, we may recolor it with a different color.

If 3 is not used on v and w, we can recolor $u_1, u_4, u_7$, if necessary, so that 3 is not used, then color u with 3. So, we may assume that v is colored 3. If w is colored 3 as well, then 1 or 2 is used at most once on $u_1,u_4,u_7$, so we may color u with the color. Thus, we may assume that w is colored 1. Now we recolor $u_4$, if necessary, with 1 or 3. Note that if one of $u_1$ and $u_7$ is not colored with 2, then we may color u with 2. Assume that both $u_1$ and $u_7$ are colored 2. Now we may recolor $u_1$ or $u_7$ with different color if $u_2$ or $u_6$ is not colored 3, so we may assume that $u_2,u_6$ are colored 3. Note that $u_2$ and $u_6$ cannot be both 4-vertices, for otherwise, $u_3, u_4, u_5$ are all 3-vertices, a contradiction to Lemma 2.2(2). It follows that $u_2$ or $u_6$ has a properly colored neighbor, so it can be recolored so that it is not colored 3, then $u_1$ or $u_7$ can be recolored so that it is not colored 2, hence we can color u with 2, a contradiction.

Case (b.2): The two 5-faces do not share a common edge. Let $[uu_1u_2u_3u_4]$ and $[u_5u_6u_7u_8u]$ be the two 5-faces, and v be the fifth neighbor of u. It follows that $u_1, u_4, u_5, u_8$ are 3-neighbors of u. By the minimality of G, $G-\{u, u_i: 1\le i\le 8\}$ can be colored, and furthermore, as each of $u_i$, $1\le i\le 8$, has at most two colored neighbors, we may properly color them. Now we try to color u.

As each of $u_1, u_4, u_5, u_8$ has at least one properly colored neighbor, they can be recolored, if necessary, with a color different from 3. So if v is not colored 3, then we can color u with 3 after recoloring the neighbors of u. Therefore, we may assume that v is colored with 3. As u cannot be colored, 1 and 2 both appear exactly twice on the neighbors of u.

Note that $u_1$ or $u_4$ is adjacent to a 3-vertex, which is properly colored. We may assume that $u_2$ is a 3-vertex and $u_1$ is colored with 1. If we can recolor $u_1$ with 2 or 3, then u can be colored with 1, so we may assume that $u_1$ cannot be recolored. It follows that $u_2$ is colored with 3, but has a properly colored neighbor, so it can be recolored differently from 3, then we can recolor $u_1$ with 3 and color u with 1, a contradiction.

(c) Suppose to the contrary that a 5-vertex u is incident with one (5, 3, 3, 4, 3)-face and three $(5,3,3,5^{+},3)$-faces. Assume that these four 5-cycles are $f_1=[uu_1u_2u_3u_4]$, $f_2=[uu_4u_5u_6u_7],f_3=[uu_7u_8u_9u_{10}]$ and $f_4=[uu_{10}u_{11}u_{12}u_{13}]$. Then $u_1u_2\ldots u_{13}$ is a path 13-path and $N(u)=\{u_1, u_4, u_7, u_{10}, u_{13}\}$ which consists of 3-vertices. Let $G'$ be the graph obtained from G by deleting u and all $4^-$-vertices in $\{u_i: 1\le i\le 13\}$. By the minimality of G, we can color all vertices of $G'$ except u and all those 3-vertices on P. Note that the 4-vertex in $\{u_i: 1\le i\le 13\}$ has only two colored neighbors, so we may properly recolor it, if necessary. Now we can properly color the 3-vertices that are not neighbors of u, and then the neighbors of u in a cyclic order. We may assume that 1 and 2 are both used twice and 3 is used once on the neighbors of u.

If the neighbor of u that is colored 3 has a properly colored neighbor, then we may recolor it with a different color and color u with 3. Similarly, if a neighbor of u that is colored 1 or 2 has two properly colored neighbors, then we may recolor it with a different color, and then color u. Since P has at most three $5^+$-vertices, u has a neighbor x that has no colored $5^+$-neighbors, that is, its two colored neighbors are both properly colored. Clearly x is colored 1 or 2, say 1. Now x can be recolored with 2 and then u can be colored with 1, a contradiction. $\square$

Lemma 2.5

• (a) A 6-vertex is incident with at most three (6, 3, 3, 4, 3)-faces.

• (b) If a 6-vertex is incident with exactly three (6, 3, 3, 4, 3)-faces, then it is incident with at most two $(6, 3, 3, 5^+,3)$-faces.

• (c) A 7-vertex is incident with at most five (7, 3, 3, 4, 3)-faces.

Proof

(a) Suppose to the contrary that a 6-vertex u is incident with four (6, 3, 3, 4, 3)-faces. We consider three cases.

Case (a.1): The vertices on the four 5-faces other than u form a 13-path $u_1u_2\ldots u_{13}$ so that $u_1, u_4, u_7$, $u_{10}$, $u_{13}$ are neighbors of u. Let v be the other neighbor of u. In this case, $[uu_1u_2u_3u_4]$, $[uu_4u_5u_6u_7]$, $[uu_7u_8u_9u_{10}]$ and $[uu_{10}u_{11}u_{12}u_{13}]$ are four (6, 3, 3, 4, 3)-faces and $N(u)-\{v\}$ consists of 3-vertices.

By the minimality of G, we may color $G-\{u, u_i: 1\le i\le 13\}$. Properly color the 4-vertices, the 3-vertices not in N(u), and the 3-neighbors of u in that order. We may assume that 1 and 2 both are used on at least two neighbors of u and 3 is used on at least one neighbor of u.

For $x\in \{u_4, u_7, u_{10}\}$, x is a 3-vertex with two properly colored neighbors, so x can be recolored with a different color (not necessarily proper anymore). For $x\in \{u_1, u_{13}\}$, x can be recolored so that it is not colored with 3 as it has a properly colored neighbor.

Let v be colored 3. We first note that 1 or 2, say 1, is used at most once on $u_1$ and $u_{13}$. Then we recolor $u_4, u_7, u_{10}$ so that 1 is not used on them. Then 1 is used at most once on the neighbors of u, and we may color u with 1, a contradiction. By symmetry, we may assume that v is colored 1. Recolor $u_1, u_4, u_7, u_{10}$ and $u_{13}$ with a color different from 3, then color u with 3.

Case (a.2): The vertices on the four 5-faces other than u form two 7-paths $u_1u_2\ldots u_7$ and $u_8u_9\ldots u_{14}$ so that $N(u)=\{u_1, u_4, u_7, u_8, u_{11}, u_{14}\}$. Then N(u) consists of 3-vertices.

By the minimality of G, we may color $G-\{u, u_i: 1\le i\le 14\}$. Properly color the 4-vertices, the 3-vertices not in N(u), and the 3-neighbors of u in that order. We may assume that 1 and 2 both are used on at least two neighbors of u and 3 is used on at least one neighbor of u.

For $x\in \{u_4,u_{11}\}$, x is a 3-vertex with two properly colored neighbors, so x can be recolored with a different color (not necessarily proper anymore). For $x\in \{u_1, u_7, u_8, u_{14}\}$, x can be recolored so that it is not colored with 3 as it has a properly colored neighbor. So we may recolor the neighbors of u so that none of them is colored 3, and then u could be colored with 3.

Case (a.3): The vertices on the four 5-faces other than u form a 10-paths $u_1u_2\ldots u_{10}$ and a 4-path $u_{11}u_{12}u_{13}u_{14}$ so that $N(u)=\{u_1, u_4, u_7, u_{10}, u_{11}, u_{14}\}$. Note that N(u) consists of 3-vertices.

By the minimality of G, we may color $G-\{u, u_i: 1\le i\le 14\}$. Properly color the 4-vertices, the 3-vertices not in N(u), and the 3-neighbors of u in the order. We may assume that 1 and 2 both are used on at least two neighbors of u and 3 is used on at least one neighbor of u.

For $x\in \{u_4, u_{7}\}$, x is a 3-vertex with two properly colored neighbors, so x can be recolored with a different color (not necessarily proper anymore). For $x\in \{u_1, u_{10}, u_{11}, u_{14}\}$, x can be recolored so that it is not colored with 3 as it has a properly colored neighbor. So we may recolor the neighbors of u so that none of them is colored 3 and color u with 3.

(b) Suppose to the contrary that a 6-vertex u is incident with six $(6, 3, 3, 4^+, 3)$-faces, only three of which are (6, 3, 3, 4, 3)-faces. Then the vertices on the six 5-faces other than u from a 18-cycle, say $u_1u_2\ldots u_{18}$, such that $N(u)=\{u_1, u_4, u_7, u_{10}, u_{13}, u_{16}\}$. By Lemma 2.2 (2), we may assume that $S=\{u_2, u_5, u_8, u_{11}, u_{14}, u_{17}\}$ is the set of $4^+$-vertices. By the minimality of G, we may color $G-(\{u, u_i: 1\le i\le 18\}-S)$. Moreover, we may recolor, if necessary, the 4-vertices in S so that they are properly colored. We can properly color the vertices in $\{u_j: u_j\notin S\cup N(u), 1\le j\le 18\}$ and then properly color the vertices in N(u).

Note that at least three neighbors of u are adjacent to two $4^-$-vertices, which are properly colored, we may recolor each of them with a different color. On the other hand, each of the other neighbors of u are adjacent to at least one properly colored neighbor, they can be recolored, if necessary, with colors different from 3. So we may recolor, if necessary, all neighbors of u so that 3 is not used, and color u with 3, a contradiction.

(c) Suppose to the contrary that a 7-vertex u is incident with six (7, 3, 3, 4, 3)-faces. Then the vertices on the six 5-faces other than u form a path $u_1u_2\ldots u_{19}$ so that $N(u)=\{u_1, u_4, u_7, u_{10}, u_{13}, u_{16}, u_{19}\}$. By the minimality of G, we may color $G-\{u, u_i: 1\le i\le 19\}$. We can then properly color the 4-vertices, the 3-vertices that are not neighbors of u, and the neighbors of u in the order. Note that each of the neighbors of u has a properly color neighbor, so they can be recolored, if necessary, with a color different from 3. Therefore, u can be colored with 3, a contradiction. $\square$

3 Proof of Theorem 1.2

To complete the proof of Theorem 1.2, we reach a contradiction by a discharging procedure. The initial charge is $\mu (x)=d(x)-4$ for $x\in V(G)\cup F(G)$. By the Euler formula, $\sum _{x\in V(G)\cup F(G)} \mu (x)=-8$.

We use the following discharging rules to redistribute charges among vertices and faces. After the discharging process, we show that the final charge $\mu ^*(x)\ge 0$ for $x\in V(G)\cup F(G)$, contrary to the fact that $\sum _{x\in V(G)\cup F(G)}\mu ^*(x)=\sum _{x\in V(G)\cup F(G)} \mu (x)=-8$.

The discharging rules are defined as follows:

• (R1) Let u be a $5^+$ vertex of G.

• (R1.1) Vertex u sends $\frac{1}{2}$ to each incident $(3,3, 5^+, 3, 4)$-face, $\frac{1}{4}$ to each incident $(3,3, 5^+, 3, 5^+)$-face.

• (R1.2) Vertex u sends $\frac{1}{2}$ to each incident $(4^-, 4^-, 5^+)$-face or $(4^-, 5^+, 5^+)$-face, and $\frac{1}{3}$ to each incident $(5^+, 5^+, 5^+)$-face.

• (R2) Let f be a $5^+$-face of G.

• (R2.1) Face f sends $\frac{1}{3}$ to each adjacent $(4^-, 4, 4)$-face, and $\frac{1}{6}$ to each adjacent $(4^-, 4^-, 5^+)$-face.

• (R2.2) Face f sends $\frac{1}{2}$ to each incident 3-vertex, and when $d(f)\ge 7$, f sends $\frac{1}{8}$ to each incident bad 5-vertex.

We shall show that each $x\in V(G)\cup F(G)$, $\mu ^{*}(x)\ge 0$. We first assume that G is 2-connected.

We first check the final charge for $f\in F(G)$ with $d(f)=k$. Note that $k\ne 6$. Let $n_3$ be the number of 3-vertices incident with f. By Lemma 2.2(2), there are at least $\lceil \frac{k}{3}\rceil$ vertices of degree at least 4, so

$$\begin{aligned} n_3\le k-\left\lceil \frac{k}{3}\right\rceil . \end{aligned}$$

(1)

Let $f=[v_1v_2\ldots v_k]$ and $v_iv_{i+1}$ be an edge of a (3, 4, 4)-face. Note that if $d(v_i)=3$, then $d(v_{i-1})\ge 4$ by Lemma 2.2(5) and $v_{i+1}$ is adjacent to a $5^+$-vertex or an isolated 4-vertex by Lemma 2.2(6) and (7); and if $d(v_i)=d(v_{i+1})=4$, then each of $v_i$ and $v_{i+1}$ is adjacent to a $5^+$-vertex or an isolated 4-vertex. This implies that

Property (A): two (3, 4, 4)-faces adjacent to f do not share vertices on f, and the 3-vertex on f and on a (3, 4, 4)-face must be between two $4^+$-vertices on f.

Let $k=3$. By Lemma 2.1, every 3-face is adjacent to three $7^{+}$-faces. By Lemma 2.2(2) and (4), f is either a $(4^{-},4,4)$-face or $(4^{-},4^{-},5^{+})$-face or $(4^{-},5^{+},5^{+})$-face or $(5^{+},5^{+},5^{+})$-face. If f is a $(4^-, 4, 4)$-face, then $\mu ^*(f)=3-4+3\cdot \frac{1}{3}=0$ by (R2.1). If f is a $(4^-, 4^-, 5^+)$-face, then f receives $\frac{1}{6}$ from each $7^+$-face by (R2.2) and $\frac{1}{2}$ from a $5^+$-vertex by (R1.2), so $\mu ^*(f)=3-4+3\cdot \frac{1}{6}+\frac{1}{2}=0$. If f is a $(4^-, 5^+, 5^+)$-face, then f receives $\frac{1}{2}$ from each $5^+$-vertex by (R1.2), so $\mu ^*(f)=-1+2\cdot \frac{1}{2}=0$. If f is a $(5^+, 5^+, 5^+)$-face, then f receives $\frac{1}{3}$ from each $5^+$-vertex by (R1.2), thus, $\mu ^*(f)=-1+3\cdot \frac{1}{3}=0$.

Let $k=4$. As 4-faces are not involved in the discharging process, $\mu ^{*}(f)=\mu (f)=d(f)-4=4-4=0$.

Let $k=5$. By (1), $n_3\le 3$. If $n_3=3$, then by Lemma 2.3, f is a $(5^+, 3, 3, 4, 3)$-face or $(5^+, 3, 3, 5^+, 3)$-face. By Lemma 2.1, f is not adjacent to any 3-face. By (R2.2), f sends $\frac{1}{2}$ to each incident 3-vertex. By (R1.1), f gets $\frac{1}{2}$ from the incident $5^{+}$-vertex in the former case, and gets $\frac{1}{4}$ from each of the incident $5^{+}$-vertices by (R1.1) in the latter case. Then $\mu ^{*}(f)\ge 1-3\cdot \frac{1}{2}+\min \{\frac{1}{2}, 2\cdot \frac{1}{4}\}=0$. If $n_3\le 2$, then f sends out at most $2\cdot \frac{1}{2}$ to incident 3-vertices. Thus, $\mu ^*(f)\ge 1-2\cdot \frac{1}{2}=0$.

Now we consider the case that $d(f)=k\ge 7$. For the sake of counting, we claim that f sends out no more than what the following rule does.

(R2*) f gives $\frac{2}{3}$ to each incident 3-vertex on a 3-face, $\frac{1}{2}$ to each of the other 3-vertices, $\frac{1}{3}$ to each incident 4-vertex in a $(4^-,4,4)$-face, and $\frac{1}{8}$ to each incident bad 5-vertices.

Indeed, by (R2.2), f sends $\frac{1}{2}$ to each incident 3-vertex, nothing to each incident 4-vertex, and $\frac{1}{8}$ to each incident bad 5-vertex, while by (R2.1) it sends $\frac{1}{3}$ to an adjacent $(4^-, 4, 4)$-face and $\frac{1}{6}$ to an adjacent $(4^-, 4^-, 5^+)$-face. Thus, by $(\hbox {R}2^*)$, f gives out an extra $\frac{1}{3}$ to the 3-vertex on each (3, 4, 4)-face; f gives out an extra $(\frac{1}{3}+\frac{1}{3})/2=\frac{1}{3}$ to the two 4-vertices on each (4, 4, 4)-face; f gives out an extra $\frac{1}{3}$ to the 3-vertices on each $(3,4^-,5^+)$-face. This means that f sends out more charges by $(\hbox {R}2^*)$ than by (R2).

Thus, by $(\hbox {R}2^*)$, the final charge of f is

$$\begin{aligned} \mu ^*(f)\ge k-4-\frac{2}{3}n_3-\frac{1}{3}(k-n_3)=\frac{2}{3}k-4-\frac{1}{3}n_3. \end{aligned}$$

(2)

Clearly, when $k\ge 9$, $\mu ^*(f)\ge \frac{2}{3}k-4-\frac{1}{3}(k-\lceil \frac{k}{3}\rceil ) =\frac{1}{3}(k+\lceil \frac{k}{3}\rceil )-4\ge 0$ since $n_3\le k-\lceil \frac{k}{3}\rceil$. So we may just consider $k\in \{7,8\}$.

Let $k=7$. Note that $\mu ^*(f)\ge \frac{2}{3}\cdot 7-4-\frac{1}{3}n_3$ by (2) and $n_3\le 4$ by (1). So $\mu ^*(f)\ge 0$ if $n_3\le 2$. Since G has no 6-cycle, a 3-face incident with a bad 5-vertex is adjacent to two $7^+$-faces and a 5-face incident with a bad 5-vertex is adjacent to a 5-face and a $7^+$-face. Thus, if f is incident with a bad 5-vertex, then it must be adjacent to a 3-face and a 5-face.

First let $n_3=3$. As each 3-vertex can only be in at most one triangle, f is adjacent to at most five 3-faces, and among them, at most three could be (3, 4, 4)-faces by Property (A). Assume that f has t adjacent (3, 4, 4)-faces. Then $t\le 3$ and there are at most $4-t$ bad 5-vertices on f, so by (R2),

$$\begin{aligned} \mu ^*(f)\ge 7-4-\frac{1}{2}\cdot 3-\frac{1}{3}t-\frac{1}{6}(5-t)-\frac{1}{8}(4-t) =\frac{1}{6}-\frac{1}{24}t\ge \frac{1}{6}-\frac{3}{24}>0. \end{aligned}$$

Now let $n_3=4$. It follows that f is either a $(3, 3, 4^+, 3, 3, 4^+, 4^+)$-face or a $(3,3,4^+,3,4^+,3,4^+)$-face by Lemma 2.2(2).

In the former case, f is clearly incident with at most three bad 5-vertices. If f is incident with three bad 5-vertices, then by Lemma 2.2(5), f is adjacent to at most two 3-faces, one being a $(3^+, 5, 5)$-face and the other a $(3, 3^+, 5)$-face, hence $\mu ^*(f)\ge 7-4-4\cdot \frac{1}{2}-3\cdot \frac{1}{8}-\frac{1}{6}=\frac{11}{24}$ by (R2). If f is incident with exactly two bad 5-vertices, then by Property (A) f is incident with at most three 3-faces and none of which is $(4^-, 4, 4)$-face. In this case, $\mu ^*(f)\ge 7-4-4\cdot \frac{1}{2}-(3\cdot \frac{1}{6} +2\cdot \frac{1}{8})>0$. If f is incident with exactly one bad 5-vertices, then by Property (A) f is incident with four 3-faces, at most one of which is $(4^-, 4, 4)$-face. In this case, $\mu ^*(f)\ge 7-4-4\cdot \frac{1}{2}-(\frac{1}{3}+3\cdot \frac{1}{6} +1\cdot \frac{1}{8})>0$. Finally, assume that f has no bad 5-vertex. As each 3-vertex can be in at most one 3-face, f is adjacent to at most five 3-faces, and by Property (A), f is adjacent to at most one $(4^-, 4, 4)$-face. Hence by (R2), $\mu ^*(f)\ge 7-4-4\cdot \frac{1}{2}-(\frac{1}{3}+4\cdot \frac{1}{6})=0.$

In the latter case, f is adjacent to at most four 3-faces since every 3-vertex on f is incident with at most one 3-face. Moreover, by Property (A), no (3, 4, 4)-face is incident with each of the two adjacent 3-vertices on f, hence f is adjacent to at most two $(4^-,4,4)$-faces, if any, a (3, 4, 4)-face. Note that if f is adjacent to exactly four 3-faces, then f has no bad 5-vertex by Lemma 2.1. Let t be the number of (3, 4, 4)-faces adjacent to f. Then, by (R2),

$$\begin{aligned} \mu ^*(f) \ge \left\{ \begin{array}{ll} 7-4-4\cdot \frac{1}{2}-2\cdot \frac{1}{3}-2\cdot \frac{1}{6}=0, &{}\quad \text { if } t=2,\\ 7-4-4\cdot \frac{1}{2}-1\cdot \frac{1}{3}-3\cdot \frac{1}{6}-1\cdot \frac{1}{8}>0, &{}\quad \text { if } t=1,\\ 7-4-4\cdot \frac{1}{2}-\max \left\{ 4\cdot \frac{1}{6},3\cdot \frac{1}{6}+3\cdot \frac{1}{8}\right\} >0, &{}\quad \text { if } t=0. \end{array} \right. \end{aligned}$$

Let $k=8$. Note that $\mu ^*(f)\ge 8\cdot \frac{2}{3}-4-\frac{1}{3}n_3$ by (2) and $n_3\le 5$ by (1). So if $n_3<5$, then $\mu ^*(f)\ge 0$. Therefore, we may assume that $n_3=5$. It follows that f is a $(3,3, 4^+,3,3,4^+,3,4^+)$-face by Lemma 2.2(2). As each 3-vertex can only be in at most one 3-face, there are at most five 3-faces adjacent to f, and among them, at most one could be a $(4^-, 4, 4)$-face by Property (A). So f gives at most $\frac{1}{3}+4\cdot \frac{1}{6}=1$ to adjacent 3-faces by (R2.1). As there are at most three bad 5-vertices, $\mu ^*(f)\ge 8-4-5\cdot \frac{1}{2}-1-3\cdot \frac{1}{8}>0$ by (R2).

Now we consider the vertices. Let u be a vertex of G. Recall that $m_i(u)$ is the number of i-faces incident with u.

• (1) $d(u)=3$. Then u is incident with at least two $5^+$-faces by Lemma 2.1. By (R2.3), $\mu ^{*}(u)\ge 3-4+\frac{1}{2}\cdot 2=0$

• (2) $d(u)=4$. Then $\mu ^{*}(u)=\mu (u)=d(u)-4=4-4=0$.

• (3) $d(u)=5$. By Lemma 2.1, $m_{3}(u)\le 2$.

  If $m_{3}(u)=2$, then u is not incident with 5-faces, so $\mu ^{*}(u)\ge 5-4-2\cdot \frac{1}{2}=0$ by (R1.2). If $m_{3}(u)=1$, then u is incident with at most two 5-faces and at least two $7^+$-faces. If u is indeed incident with two 5-faces, then one is a $(5, 3^+,3^+,4^+,3^+,)$-face and the other is a $(5, 3^+,3^+,5^+,3^+)$-face by Lemmas 2.2(2), 2.3 and 2.4 (b). By (R1.1) and (R2.2), if u is not bad, then it gives at most $\max \{\frac{1}{2}, 2\cdot \frac{1}{4}\}=\frac{1}{2}$ to the 5-faces, and if u is a bad 5-vertex, then it gives $\frac{1}{2}+\frac{1}{4}$ to the 5-faces and gets $\frac{1}{8}$ from each of the incident $7^{+}$-faces. Therefore, by (R1), $\mu ^{*}(u)\ge 1-\frac{1}{2}-\frac{1}{2}-\frac{1}{4}+ 2\cdot \frac{1}{8}=0$. Let $m_{3}(u)=0$. If u is incident with a (3, 3, 5, 3, 4)-face, then u is incident with exactly one (3, 3, 5, 3, 4)-face by Lemma 2.4 (b) and at most two $(3,3,5,3,5^{+})$-faces by Lemma 2.4 (c); and if u is not incident with any (3, 3, 5, 3, 4)-face, then u is incident with at most four $(3,3,5,3,5^{+})$-faces by Lemma 2.4 (a). Thus, $\mu ^{*}(u)\ge 1-\max \{\frac{1}{2}+2\cdot \frac{1}{4}, 4\cdot \frac{1}{4}\}=0$ by (R1).

• (4) $d(u)\ge 6$. By (R1), u gives at most $\frac{1}{2}$ to each incident 3- or 5-face. If $m_{3}(u)\ne 0$, then $m_{3}(u)+m_{5}(u)\le d(u)-2$, so

  $$\begin{aligned} \mu ^{*}(u)\ge & {} d(u)-4-\frac{1}{2}(m_{3}(u)+m_{5}(u))\ge d(u)-4-\frac{1}{2}(d(u)-2)=\frac{1}{2}d(u)\\ -3\ge & {} 6\cdot \frac{1}{2}-3=0. \end{aligned}$$

  Thus, we may assume that $m_{3}(u)=0$. If $d(u)\ge 8$, then $\mu ^{*}(u)\ge d(u)-4-\frac{1}{2}m_{5}(u)\ge d(u)-4-\frac{1}{2}d(u)=\frac{1}{2}d(u)-4\ge 8\cdot \frac{1}{2}-4=0.$ If $d(u)=7$, then by Lemma 2.5 (c), u is incident with at most five (7, 3, 3, 4, 3)-faces, so by (R1.1), $\mu ^*(u)\ge 7-4-5\cdot \frac{1}{2}-2\cdot \frac{1}{4}=0$. Let $d(u)=6$. Then u is incident with at most three (3, 3, 6, 3, 4)-faces by Lemma 2.5 (a), and when it is incident with three (6, 3, 3, 4, 3)-faces, it is incident with at most two $(3,3,6,3,5^{+})$-faces by Lemma 2.5 (b). If u is incident with l (3, 3, 6, 3, 4)-faces, where $0\le l\le 2$ , then it is incident with at most $6-l$ $(3, 3, 6, 3, 5^+)$-faces. Thus, $\mu ^{*}(u)\ge 6-4-\max \{3\cdot \frac{1}{2}+ 2\cdot \frac{1}{4}, 2\cdot \frac{1}{2}+ 4\cdot \frac{1}{4}, \frac{1}{2}+5\cdot \frac{1}{4}, 6\cdot \frac{1}{4}\}=0$ by (R1).

So far, we have proved that if G is 2-connected, then G is (1, 1, 0)-colorable. Thus, we assume that G has cut vertices. Let $B_1, B_2, \ldots , B_t$ be the blocks of G such that for each i, $B_i$ has only one cut vertex $b_i$ of G and let $u_i\in V(B_i)\setminus \{b_i\}$. Clearly $t\ge 2$. Let $G'$ be the graph obtained from G by adding a new vertex u and edges $uu_1, uu_2,\ldots , uu_t$. If each cycle of $G'$ containing u has length at least 7, let $G^*=G'$. Thus, assume that C is a cycle of $G'$ which contains u and some vertex $u_i$ where $1\le i\le t$ and the length of C is less than 7. In this case, we take a copy, denoted by $B_i'$, of $B_i$. Let $u_i'$ and $b_i'$ of $B_i'$ be the corresponding vertices of $u_i$ and $b_i$ in $B_i$. Let $G''$ be the graph obtained from $G'$ by deleting edge $uu_i$, then by identifying $u_i$ in $B_i$ with $b_i'$ in $B_i'$ and adding an edge joining u to $u_i'$ in $B_i'$. It is clear that $G''$ has a cycle containing u which has length more than one than its corresponding cycle in $G'$. Keeping this procedure until the resulting graph, denoted by $G^*$, has the property: each cycle of $G^*$ containing u has length at least 7. Obviously, $G^*$ is a 2-connected plane graph, $G^*$ has without 3-cycle adjacent to 4-cycle and without 6-cycle, and G is a subgraph of $G^*$. Thus, $G^*$ is (1, 1, 0)-colorable and so is G.