A graph is near-bipartite if its vertex set can be partitioned into two parts such that one part is an independent set and the other induces a forest. It is clear that near-bipartite graphs are 3-colorable. It was proved that planar graphs without 4-, 5– and 8-cycles are 3-colorable [Discuss. Math. Graph Theory, 31(2011): 775-789]. It is asked by Kang et al that whether it is true that the planar graphs without 4-, 5– and 8-cycles are near-bipartite [Discuss. Math. Graph Theory 45 (2025) 129-145]. A 6-cycle is called a special 6-cycle if this 6-cycle shares an edge with a triangle of G. In this paper, we prove that planar graphs without 4-, 5-, 8-cycles and special 6-cycles are near-bipartite which is a step toward the problem.
A graph \(G\) is \(k\)-degenerate if every subgraph \(H\) of \(G\) contains a vertex of degree at most \(k\) in \(H\). Clearly, every \(k\)-degenerate graph is \((k+1)\)-colorable. Borodin [1] in 1976 suggested to partition the vertex set of a graph into two sets such that the induced subgraphs have good degeneracy properties. A graph \(G\) is \((a,b)\)-partitionable if its vertices can be partitioned into sets \(A\) and \(B\) such that the subgraph induced by \(A\) is \(a\)-degenerate and the subgraph induced by \(B\) is \(b\)-degenerate. Borodin [1] conjectured that every planar graph, which is \(5\)-degenerate, is \((1,2)\)– and \((0,3)\)-partitionable. Thomassen [7] [8] confirmed these conjectures.
Clearly a graph is bipartite if and only if it is \((0,0)\)-partitionable. A graph is called near-bipartite if it is \((0,1)\)-partitionable. Borodin and Glebov [2] showed that every planar graph of girth at least \(5\) is near-bipartite. Dross, Montassier, and Pinlou [3] asked whether every triangle-free planar graph is near-bipartite. Liu and Yu [5] showed that planar graphs without cycles of lengths in \(\{4,6,8\}\) are near-bipartite, which extend the result of Wang and Chen [9] that they are \(3\)-colorable. Mondal [6] showed that planar graphs without \(4\)-, \(5\)-, \(8\)-cycles are \(3\)-colorable. Kang et al. [4] proved that every planar graph with neither \(4\)– and \(6\)-cycles nor special \(9\)-cycles are near-bipartite and asked that whether it is true that the planar graphs without \(4\)-, \(5\)– and \(8\)-cycles are near-bipartite. A \(6\)-cycle is called a special \(6\)-cycle if this \(6\)-cycle shares an edge with a triangle of \(G\). In this paper, in order to ask the question of Kang, we show that planar graphs without \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles are near-bipartite as the following theorem.
Theorem 1.1. Every planar graph without \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles are near-bipartite.
An \(IF\)-coloring of a graph is a partition of its vertices into two parts such that one part colored \(I\) induces an independent set and the other part colored \(F\) induces a forest. A path or cycle on only \(F\)-vertices is called an \(F\)-path or \(F\)-cycle, respectively. Given a graph \(G\) and a cycle \(C\) in \(G\), an \(IF\)-coloring \(\phi_c\) of \(G[V(C)]\) super-extends to \(G\) if there exists an \(IF\)-coloring \(\phi_G\) of \(G\) that extends \(\phi_c\) with the property that there is no \(F\)-path with at least three vertices which has two end-vertices on \(C\) and all other vertices not on \(C\). We say that \(C\) is super-extendable to \(G\) if every \(IF\)-coloring \(\phi_c\) of \(G[V(C)]\) can super-extend to \(G\). A \(12\)-cycle \([v_{1}v_{2}\cdots v_{12}v_{1}]\) of a plane graph is called bad if its interior or exterior contains a common neighbor \(x\) of \(v_{1}\), \(v_{5}\) and \(v_{9}\) (see Figure 1).
In Figure 1, we call \(x\) the center vertex of the bad cycle \(C\). Instead of Theorem 1.1, we actually prove the following stronger result.
Theorem 1.2. For every plane graph \(G\) without \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles, given any cycle \(C\) in \(G\) of length at most \(12\) except bad cycles, \((G,C)\) is super-extendable.
By [2], every planar graph of girth \(5\) has an \(IF\)-coloring. Since \(G\) contains no \(4\)-cycles, \(G\) must have a triangle which is a good cycle. Thus Theorem 1.1 follows from Theorem 1.2 easily.
The graphs considered in this paper are finite and simple. A vertex is classified as an external vertex if it lies on the boundary of the unbounded face; otherwise, it is considered to be internal. For a cycle \(C\), let \(int(C)\) and \(ext(C)\) denote the set of vertices in the interior and exterior of \(C\), respectively. A cycle \(C\) is separating if both \(int(C)\) and \(ext(C)\) are nonempty. Let \(d(v)\) be the degree of \(v\). A \(k\)-vertex (\(k^{+}\)-vertex, \(k^{-}\)-vertex) is a vertex of degree \(k\) (at least \(k\), at most \(k\)). A \(k\)-face (\(k^{+}\)-face, \(k^{-}\)-face) is a face of degree \(k\) (at least \(k\), at most \(k\)). A \(k\)-cycle (\(k^{+}\)-cycle, \(k^{-}\)-cycle) is a cycle of degree \(k\) (at least \(k\), at most \(k\)).
Let (\(G\), \(C_0\)) be a counterexample to Theorem 1.2 with the minimum value about \(\lvert V(G) \rvert + \lvert E(G) \rvert\), where \(C_0\) is a cycle of length at most \(12\) in \(G\) and not a bad cycle that is precolored for \(G[V(C)]\). If \(C_0\) is a separating cycle, then \(C_0\) is super-extendable to both \(G – ext(C_0)\) and \(G – int(C_0)\). Thus, \(C_0\) is super-extendable to \(G\), contrary to the choice of \(C_0\). So we may assume that \(C_0\) is the boundary of the outer face of \(G\) in the rest of this paper. Call a vertex \(v\) internal if \(v \notin C_0\) and a face \(f\) internal if \(f \neq C_0\). We have the following lemmas about the counterexample \(G\).
Lemma 2.1. Every internal vertex of \(G\) has degree at least \(3\).
Proof. Suppose to the contrary that \(G\) has an internal vertex \(v\) such that \(d(v)\leq 2\). By the minimality of (\(G\), \(C_0\)), the \(IF\)-coloring of \(C_0\) can super-extend to \(G-v\). If \(v\) has a neighbor colored \(I\), then color \(v\) with \(F\); otherwise, color \(v\) with \(I\). In all cases, \(C_0\) can super-extend to \(G\), a contradiction. ◻
Lemma 2.2. Except for the bad cycles, the graph \(G\) has no separating cycle of length at most \(12\).
Proof. Suppose otherwise that \(C\) is a separating cycle of length at most \(12\) but not the bad cycle and \(C \neq C_0\). Let \(H_{1}=G-int(C)\) and \(H_{2}=G[C \cup int(C)]\). By the minimality of \(G\), (\(H_{1}\), \(C_0\)) is super-extendable, and after that, \(G[V(C)]\) is colored. By the minimality of (\(G\),\(C_0\)) again, (\(H_{2}\), \(C\)) is super-extendable. Further, we get that (\(G\), \(C_0\)) is super-extendable, a contradiction. ◻
Lemma 2.3. \(C_0\) has no chords.
Proof. If \(C_0\) has a chord, then by Lemma 2.2, \(V(C_0)=V(G)\). By our assumption, the precoloring of \(C_0\) is already a \(IF\)-coloring of \(G\). ◻
A vertex (or an edge) is triangular if it is incident with a triangle. We say that a vertex is bad if it is an internal triangular \(3\)-vertex; otherwise, it is a good vertex. A tetrad in a plane graph is a path \(v_{1}v_{2}v_{3}v_{4}\) of four internal \(3\)-vertices contained in the boundary of a face, so that both \(v_{1}v_{2}\) and \(v_{3}v_{4}\) are edges of triangles (see Figure 2).
Lemma 2.4. \(G\) contains no tetrad.
Proof. Let \(v_{1}v_{2}v_{3}v_{4}\) be a tetrad in \(G\) (see Figure 2), \(N(v_{1})\)=\(\{x,v_{2},v_{1}^{'}\}\) and \(N(v_{4})\)=\(\{y,v_{3},v_{4}^{'}\}\). Let \(G^{'}\) be the graph obtained by identifying \(y\) and \(v_{1}^{'}\) of \(G\)–\(\{v_{1},v_{2},v_{3},v_{4}\}\). Let \(v^{*}\) denote the new vertex obtained by identifying \(y\) and \(v_{1}'\).
Note that the identification does not create a chord of \(C_0\) or identify two vertices of \(C_0\). Suppose the identification does create a chord, then either \(y\) or \(v_{1}^{'}\) must be on \(C_0\). Without the loss of generality, assume that \(v_{1}^{'}\in C_0\) and \(y^{'}\in C_0\) which is a neighbor of \(y\) different from \(v_{3}\) and \(v_{4}\). There exists a path \(P\)= \(y^{'}yv_{3}v_{2}v_{1}v_{1}^{'}\) that divides \(C_0\) into two parts \(P_{1}\) and \(P_{2}\). Obviously, \(x\) is not on \(C_0\) since \(G\) has neither \(4\)-, \(5\)-, \(8\)-cycles nor special \(6\)-cycles. Since \(\lvert C_0 \rvert\) \(\leq 12\), \(\lvert P_{1} \rvert\) + 5 + \(\lvert P_{2} \rvert\)+ 5 \(\leq\) 22. Then either \(P\cup P_{1}\) or \(P\cup P_{2}\) is a cycle of length at most \(11\) that separates \(x\) and \(v_{4}\), a contradiction to Lemma 2.2.
In \(G-\{v_{1},v_{2},v_{3},v_{4}\}\), we will prove that there is no path \(Q\) of length at most \(8\) between \(y\) and \(v_{1}^{'}\). For otherwise, assume that \(\lvert\)\(Q\)\(\rvert\)\(\leq\)8. Then \(Q\cup yv_{3}v_{2}v_{1}v_{1}^{'}\) would have a cycle of length at most \(12\) of \(G\). Obviously, this cycle separates \(x\) and \(v_{4}\) since \(x\) is not on \(Q\) by the assumption that \(G\) has no \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles. In addition, we claim that the separation cycle cannot be a bad cycle as follows, thus we get a contradiction to Lemma 2.2. If \(C=Q\cup yv_{3}v_{2}v_{1}v_{1}^{'}\) is a bad \(12\)-cycle and \(x\) is inside \(C\), it is impossible that \(x\) is the center vertex of \(C\). So there is another vertex \(x'\) inside \(C\) which is the center vertex of \(C\). Note that \(v_{1}v_{2}v_{3}v_{4}\) is a tetrad of \(G\). Both \(v_{1}'\) and \(y\) are adjacent to \(x'\). Then \(v_{1}'x'yv_{3}v_{2}v_{1}v_{1}'\) separates \(x\) and \(v_{4}\), a contradiction. If \(C=Q\cup yv_{3}v_{2}v_{1}v_{1}^{'}\) is a bad \(12\)-cycle and \(x\) is outside \(C\), it is impossible that \(v_{4}\) is the center vertex of of the bad cycle \(C\). So there is another vertex \(t\) inside \(C\) which is the center vertex of of the bad cycle \(C\). Note that \(v_{1}v_{2}v_{3}v_{4}\) is a tetrad of \(G\). Both \(v_{1}'\) and \(y\) are adjacent to \(t\). Then \(v_{1}'tyv_{3}v_{2}v_{1}v_{1}'\) separates \(x\) and \(v_{4}\), still a contradiction. So there is no path \(Q\) of length at most \(8\) between \(y\) and \(v_{1}^{'}\) in \(G-\{v_{1},v_{2},v_{3},v_{4}\}\) and no new \(8^{-}\)-cycles are created in \(G^{'}\). This implies that \(G^{'}\) contains no \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles. Since \(\lvert V(G^{'}) \rvert\) <\(\lvert V(G) \rvert\), the precoloring of \(C_0\) can be super-extended to a \(IF\)-coloring of \(G^{'}\). Now we will super-extend it to an \(IF\)-coloring of \(G\).
First, we color \(v_{1}'\) and \(y\) with the color of the identified vertex. If \(v_{1}'\), \(y\) are colored \(I\), then color \(v_{1}\), \(v_{3}\), \(v_{4}\) with \(F\) and color \(v_{2}\) with a color different from the color of \(x\). If \(v_{1}'\), \(y\) are colored \(F\) and \(x\) is colored \(I\), then both \(v_{1}\) and \(v_{2}\) are colored \(F\). Next we discuss the color of \(v_{4}'\). If \(v_{4}'\) is colored \(I\), then \(v_{4}\) is colored \(F\) and \(v_{3}\) is colored \(I\), we are done. If \(v_{4}'\) is colored \(F\), then \(v_{4}\) is colored \(I\) and \(v_{3}\) is colored \(F\). Notice that \(yv_{3}v_{2}v_{1}v_{1}'\) might be one part of an \(F\)-path, but this is impossible. Suppose not, \(G^{'}\) would also have an \(F\)-path, a contradiction. If \(v_{1}'\), \(y\) are colored \(F\) and \(x\) is also colored \(F\). Next we discuss the color of \(v_{4}'\). If \(v_{4}'\) is colored \(I\), then both \(v_{4}\) and \(v_{2}\) are colored \(F\), both \(v_{1}\) and \(v_{3}\) are colored \(I\), we are done. If \(v_{4}'\) is colored \(F\), there are the following two cases.
Case 1. Assume that there is an \(F\)-path \(P\) between \(x\) and \(y\) in the \(IF\)-coloring of \(G^{'}\). Then both \(v_{1}\) and \(v_{3}\) are colored \(F\), both \(v_{2}\) and \(v_{4}\) are colored \(I\). We are done as follow. Notice that \(P_{1}v_{1}'v_{1}xP_{2}\) or \(P_{1}v_{1}'v_{1}xPP_{3}\) may form an \(F\)-path which has two end-vertices on \(C_{0}\) and all other vertices are not on \(C_{0}\) (see Figure 3). In Figure 3, \(C_{0}\) is the outer cycle. But this is impossible. Otherwise, the coloring of \(G^{'}\) would also form an \(F\)-path \(P_{1}v^{*}PxP_{2}\) or \(P_{1}v^{*}P_{3}\) which has two end-vertices on \(C_{0}\) and all other vertices are not on \(C_{0}\), a contradiction. In addition, \(P_{4}v_{1}'v_{1}x\) may form an \(F\)-cycle. Then this is also impossible. Suppose not, the coloring of \(G^{'}\) would also form an \(F\)-cycle \(xP_{4}v^{*}Px\), a contradiction.
Case 2. Assume that there is no \(F\)-path \(P\) between \(x\) and \(y\) in the \(IF\)-coloring of \(G^{'}\). Then both \(v_{2}\) and \(v_{3}\) are colored \(F\), both \(v_{1}\) and \(v_{4}\) are colored \(I\). We are done as follow. Notice that \(P_{2}xv_{2}v_{3}yP_{3}\) may form an \(F\)-path which has two end-vertices on \(C_{0}\) and all other vertices are not on \(C_{0}\) (see Figure 3). In Figure 3, \(C_{0}\) is the outer cycle. In this case, we re-color them: both \(v_{1}\) and \(v_{3}\) are colored \(F\), and both \(v_{2}\) and \(v_{4}\) are colored \(I\). After re-coloring, we still need to note that \(P_{1}v_{1}'v_{1}xP_{2}\) may form an \(F\)-path which has two end-vertices on \(C_{0}\) and all other vertices are not on \(C_{0}\) (see Figure 3). But this is impossible. Otherwise, the coloring of \(G^{'}\) would also form an \(F\)-path \(P_{1}v^{*}P_{3}\) which has two end-vertices on \(C_{0}\) and all other vertices are not on \(C_{0}\), a contradiction. In addition, \(P_{4}v_{1}'v_{1}x\) may form an \(F\)-cycle. Then this is also impossible. Suppose not, the coloring of \(G^{'}\) would also form an \(F\)-path \(P_{2}xP_{4}v^{*}P_{3}\) which has two end-vertices on \(C_{0}\) and all other vertices are not on \(C_{0}\), a contradiction. ◻
We are now ready to present a discharging procedure that will complete the proof of Theorem 1.2. Let \(x \in V(G) \cup (F(G)-C_0)\) have an initial charge of \(ch(x)=d(x)-4\), and \(ch(C_0) = \lvert C_0 \rvert + 4\). By Euler’s Formula, \(\sum\limits_{x_\in V\cup F} ch(x)\)=0. Let \(ch^{*}(f)\) be the charge of \(x\in V\cup F\) after the discharge procedure. To lead to a contradiction, we shall prove that \(ch^{*}(x) \geq 0\) for all \(x\in V(G)\cup (F(G)-C_{0})\) and \(ch^{*}(C_0) > 0\).
Here are the discharging rules:
\((R1)\). Each \(3\)-face gets \(\frac{1}{3}\) from each incident vertex.
\((R2)\). (a) Let \(v\) be an external 2-vertex. \(v\) gets \(\frac{2}{3}\) from the internal face containing \(v\).
(b) Let \(v\) be an internal 3-vertex. If \(v\) is a bad vertex, then \(v\) gets \(\frac{2}{3}\) from each \(9^{+}\)-face containing \(v\). Otherwise, \(v\) gets \(\frac{1}{3}\) from each \(6^{+}\)-face containing \(v\).
(c) Let \(v\) be an internal 4-vertex. If \(v\) is incident with only one \(3\)-face, then \(v\) gets \(\frac{1}{3}\) from the unique face \(f\) which contains \(v\) and is not adjacent to this \(3\)-face; if \(v\) is incident with two \(3\)-faces, then \(v\) gets \(\frac{1}{3}\) from each \(9^{+}\)-face containing \(v\).
\((R3)\). Each \(3\)-vertex on \(C_0\) which is not in a triangle gives \(\frac{1}{6}\) to each incident internal \(6\)–face. Each \(4^{+}\)-vertex on \(C_0\) gives \(\frac{1}{6}\) to each incident internal \(6\)-face.
\((R4)\). The outer face \(C_0\) gives \(\frac{4}{3}\) to each incident \(2\)-vertex or \(3\)-vertex, and 1 to each other incident vertex.
After the discharging of rules from (R1) to (R4) is completed, the discharging of rule (R5) is performed.
\((R5)\). Each internal face adjacent to \(C_0\) gives the surplus charge to \(C_0\).
Lemma 3.1. Every vertex \(v\) in \(G\) has nonnegative final charge.
Proof. Let \(d(v)=2\). Then \(v\in C_0\) by Lemma 2.1. By (R4), \(v\) gets \(\frac{4}{3}\) from \(C_0\). By (R2), \(v\) gets \(\frac{2}{3}\) from the other incident face. So \(ch^{*}(v) \geq 2 – 4 + \frac{4}{3} + \frac{2}{3}=0\).
Let \(d(v)=3\). If \(v\in C_0\) and \(C_0\) is a \(3\)-face, there are two \(9^{+}\)-faces containing \(v\). By (R1), \(v\) gives \(\frac{1}{3}\) to \(C_0\). By (R4), \(v\) also gets \(\frac{4}{3}\) from \(C_0\). So \(ch^{*}(v)\geq 3 – 4 + \frac{4}{3}-\frac{1}{3}=0\). If \(v\in C_0\) and \(C_0\) is a \(6\)-face or \(7\)-face, there are exactly two internal \(6^{+}\)-faces containing \(v\) since \(G\) has no \(8\)-cycles and special \(6\)-cycles. By (R4), \(v\) also gets \(\frac{4}{3}\) from \(C_0\). By (R3), \(v\) gives at most \(\frac{1}{6}\times 2\) to its incident internal \(6\)-faces. So \(ch^{*}(v)\geq 3 – 4 + \frac{4}{3}-\frac{1}{6}\times 2=0\). If \(v\in C_0\) and \(C_0\) is a \(9^{+}\)-face, the set of degrees of the internal faces containing \(v\) is one of the following: \(\{3, 9^{+}\}\), \(\{6^{+}, 6^{+}\}\) since \(G\) has no special \(6\)-cycles and without \(4\)-, \(5\)-, \(8\)-cycles. By (R4), \(v\) gets \(\frac{4}{3}\) from \(C_0\). For the case \(\{3, 9^{+}\}\), \(v\) gives \(\frac{1}{3}\) to the inner \(3\)-face by (R1), so we have that \(ch^{*}(v)\geq 3 – 4 +\frac{4}{3}- \frac{1}{3}\geq 0\). For the case \(\{6^{+}, 6^{+}\}\), by (R3), \(v\) gives at most \(\frac{1}{6}\times 2\) to its incident internal \(6\)-faces. Then \(ch^{*}(v)\geq 3 – 4 + \frac{4}{3} – \frac{1}{6}\times 2=0\). If \(v\notin C_0\), the set of degrees of the faces containing \(v\) is one of the following: \(\{3, 9^{+}, 9^{+}\}\), \(\{6^{+}, 6^{+}, 6^{+}\}\). For the case \(\{3, 9^{+}, 9^{+}\}\), \(v\) is a bad \(3\)-vertex. By (R2), \(v\) gets \(\frac{2}{3}\times 2\) from the two incident \(9^{+}\)-faces. By (R1), \(v\) gives \(\frac{1}{3}\) to its incident \(3\)-face. For the case \(\{6^{+}, 6^{+}, 6^{+}\}\), \(v\) is not a bad \(3\)-vertex. By (R2), \(v\) gets \(\frac{1}{3}\times 3\) from the three incident faces. So we get that \(ch^{*}(v) \geq 3 – 4 + min \{ \frac{2}{3} \times 2 – \frac{1}{3}, \frac{1}{3} \times 3\}=0\).
Let \(d(v)=4\). If \(v\in C_0\) and \(C_0\) is a \(3\)-face, the sets of degrees of the internal faces containing \(v\) are \(\{9^{+}, 6^{+}, 9^{+}\}\), and \(\{9^{+},3, 9^{+}\}\) since \(G\) has no special \(6\)-cycles. For the case \(\{9^{+}, 6^{+}, 9^{+}\}\), \(v\) gets \(1\) from \(C_0\) by (R4), \(v\) gives \(\frac{1}{3}\) to \(C_0\) by (R1) and \(v\) gives at most \(\frac{1}{6}\) to the incident internal faces by (R3). Then \(ch^{*}(v)\geq 4 – 4 + 1- \frac{1}{3}- \frac{1}{6}\geq 0\). For the case \(\{9^{+},3, 9^{+}\}\), \(v\) gets \(1\) from \(C_0\) by (R4) and \(v\) gives \(\frac{1}{3}\times 2\) to the outer \(3\)-face \(C_{0}\) and the internal \(3\)-face by (R1). Then \(ch^{*}(v)\geq 4 – 4 +1- \frac{1}{3}\times 2\geq 0\). If \(v\in C_0\) and \(C_0\) is a \(6\)-face or \(7\)-face, the set of degrees of the internal faces containing \(v\) is one of the following: \(\{6^{+}, 6^{+}, 6^{+}\}\), \(\{9^{+},3, 9^{+}\}\). For the case \(\{6^{+}, 6^{+}, 6^{+}\}\), \(v\) gets \(1\) from \(C_0\) by (R4), and \(v\) gives at most \(\frac{1}{6}\times3\) to the incident internal \(6\)-faces by (R3). Then \(ch^{*}(v)\geq 4 – 4 + 1- \frac{1}{6}\times 3\geq 0\). For the cases \(\{9^{+},3, 9^{+}\}\), \(v\) gets \(1\) from \(C_0\) by (R4) and \(v\) gives \(\frac{1}{3}\) to the internal \(3\)-face by (R1). Then \(ch^{*}(v)\geq 4 – 4 +1- \frac{1}{3}\geq 0\).
If \(v\in C_0\) and \(C_0\) is a \(9^{+}\)-face, the set of degrees of the internal faces containing \(v\) is one of the following: \(\{3, 9^{+}, 3^{+}\}\), \(\{9^{+},3, 9^{+}\}\), \(\{9^{+},6, 9^{+}\}\), \(\{6^{+}, 6^{+}, 6^{+}\}\). By (R4), \(v\) gets \(1\) from \(C_0\). For the case \(\{3, 9^{+}, 3^{+}\}\), \(v\) gives the most \(\frac{1}{3}\times 2\) to the incident two \(3\)-faces by (R1). For the case \(\{9^{+},3, 9^{+}\}\), \(v\) gives \(\frac{1}{3}\) to the incident \(3\)-face by (R1). For the case \(\{9^{+},6, 9^{+}\}\), \(v\) gives \(\frac{1}{6}\) to the incident \(6\)-face by (R3). For the case \(\{6^{+}, 6^{+}, 6^{+}\}\) , \(v\) gives at most \(\frac{1}{6}\times 3\) to the incident internal faces by (R3). So \(ch^{*}(v)\)\(\geq\) 4 – 4 + min \(\{1 – \frac{1}{3} \times 2, 1 – \frac{1}{3}, 1 – \frac{1}{6}, 1 – \frac{1}{6} \times 3 \}\geq 0\).
If \(v\notin C_0\), the set of degrees of the faces containing \(v\) in clock-wise order is one of the following: \(\{3, 9^{+}, 3, 9^{+}\}\), \(\{3, 9^{+}, 6^{+}, 9^{+}\}\), \(\{6^{+}, 6^{+}, 6^{+}, 6^{+}\}\). For the case \(\{3, 9^{+}, 3, 9^{+}\}\), by (R1) and R(2), \(v\) gives \(\frac{1}{3}\) to each of the two incident 3-faces and gets \(\frac{1}{3}\) from each of the two incident \(9^{+}\)-faces. For the cases \(\{3, 9^{+}, 6^{+}, 9^{+}\}\), by (R1) and R(2), \(v\) gives \(\frac{1}{3}\) to the incident \(3\)-face and gets \(\frac{1}{3}\) from the incident \(6^{+}\)-face which is not adjacent to the \(3\)-face containing \(v\). For the case \(\{6^{+}, 6^{+}, 6^{+}, 6^{+}\}\), by (R2), do not charge value. So \(ch^{*}(v)\geq 4 – 4 + min\{\frac{1}{3}\times 2 – \frac{1}{3}\times 2, \frac{1}{3} – \frac{1}{3} \}\geq 0\).
Finally, let \(d(v) \geq 5\). If \(v\in C_0\) and \(C_0\) is a \(3\)-face, \(v\) is contained in at most \(\lfloor \frac{d(v)}{2}\rfloor\) \(3\)-faces. By (R4), \(v\) gets \(1\) from \(C_0\). By (R1), \(v\) gives at most \(\frac{1}{3}\times \lfloor\frac{d(v)}{2}\rfloor\) to all the incident \(3\)-faces. So \(ch^{*}(v)\geq d(v) – 4 + 1 – \lfloor \frac{d(v)}{2}\rfloor \times \frac{1}{3} > 0\). If \(v\in C_0\) and \(C_0\) is a \(6\)-face or \(7\)-face, \(v\) is contained in at most \(\lfloor \frac{d(v)-2}{2}\rfloor\) \(3\)-faces since \(G\) has no \(8\)-cycles and special \(6\)-cycles. When \(v\) is contained in exactly \(\lfloor \frac{d(v)-2}{2}\rfloor\) \(3\)-faces, \(v\) is contained in at most two \(6\)-faces since \(G\) has no special \(6\)-cycles. So \(ch^{*}(v)\geq d(v) – 4 + 1 – \lfloor \frac{d(v)-2}{2}\rfloor \times \frac{1}{3}- \frac{1}{6}\times2> 0\). If \(v\in C_0\) and \(C_0\) is a \(9^{+}\)-face, let \(x\) be the number of \(3\)-faces incident to \(v\). Then we have that \(x\leq \lfloor\frac{d(v)}{2}\rfloor\). By (R1) and (R3), \(ch^{*}(v)\geq d(v) – 4 + 1 – \frac{x}{3} – (x-1)\times\frac{1}{6} > 0\) or \(ch^{*}(v)\geq d(v) – 4 + 1 – d(v)\times\frac{1}{6} > 0\) . If \(v\notin C_0\), by (R1), \(v\) gives at most \(\frac{1}{3}\times \lfloor\frac{d(v)}{2}\rfloor\) to the incident 3-faces and we have that \(ch^{*}(v) \geq d(v) – 4 – \lfloor\frac{d(v)}{2}\rfloor \times \frac{1}{3} > 0\). ◻
Lemma 3.2. Every internal face in \(G\) has nonnegative final charge.
Proof. Let \(f\) be an internal face in \(G\). Recall that \(G\) contains no \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles. If \(d(f)=3\), \(f\) gets \(\frac{1}{3}\) from each incident vertex by (R1) and thus \(ch^{*}(f) \geq 3 – 4 + \frac{1}{3} \times 3 =0\).
Suppose that \(d(f)=6\). Since \(G\) contains no special \(6\)-cycles, \(f\) is not adjacent to a \(3\)-face. Hence, \(f\) has no bad \(3\)-vertex. If \(V(f) \cap C_0 = \emptyset\), by (R2), \(ch^{*}(f)\geq 6 – 4 – \frac{1}{3} \times 6 =0\). If \(V(f) \cap C_0 \neq \emptyset\), then 1 \(\leq \lvert V(f) \cap C_0 \rvert \leq\) 5 by Lemma 2.3. Further, we can easily see that \(V(f)\) \(\cap\) \(C_0\) contains at most two external \(3^{+}\)-vertices and at most three external \(2\)-vertices. When \(V(f)\) \(\cap\) \(C_0\) contains exactly three \(2\)-vertices, it must contain exactly two external \(3^{+}\)-vertices. The degree set of the two external \(3^{+}\)-vertices can have the following cases \(\{3, 3\}\), \(\{3, 4^{+}\}\), \(\{4^{+}, 4^{+}\}\). For all the cases, since \(f\) is not adjacent to a \(3\)-face, by (R2) and (R3), \(ch^{*}(f)\geq 6 – 4 – \frac{2}{3} \times 3 – \frac{1}{3} + \frac{1}{6} \times 2=0\). When \(V(f) \cap C_0\) contains less than three \(2\)-vertices, the discussion is easy.
Suppose that \(d(f)=7\). Since \(G\) contains no \(8\)-cycle, \(f\) is not adjacent to a \(3\)-face. Hence, \(f\) has no bad \(3\)-vertex. If \(V(f) \cap C_0 = \emptyset\), by (R2), \(ch^{*}(f)\geq 7 – 4 – \frac{1}{3} \times 7\geq 0\). If \(V(f) \cap C_0 \neq \emptyset\), then 1 \(\leq \lvert V(f) \cap C_0 \rvert \leq\) 6 by Lemma 2.3 and \(V(f) \cap C_0\) contains at most four \(2\)-vertices. If there are exactly four \(2\)-vertices in \(V(f)\) \(\cap\) \(C_0\), then there must be two external \(3^{+}\)-vertices in \(V(f)\) \(\cap\) \(C_0\). The degree sets of the two external \(3^{+}\)-vertices are \(\{3, 3\}\), \(\{3, 4^{+}\}\) and \(\{4^{+}, 4^{+}\}\). For all the cases, since \(f\) is not adjacent to a \(3\)-face, by (R2), \(ch^{*}(f)\geq 7 – 4 – \frac{2}{3}\times 4-\frac{1}{3} \geq 0\). If there are at most three \(2\)-vertices in \(V(f)\) \(\cap\) \(C_0\), the discussion is the same as above.
Suppose that \(d(f)=9\). If \(V(f) \cap C_0 = \emptyset\), by Lemma 2.4, \(f\) contains at most seven bad \(3\)-vertices. In addition, we may assume that the other two vertices are internal \(4\)-vertices (see Figure 4). Then, by (R2), \(f\) gives \(\frac{2}{3}\) to each bad \(3\)-vertex and gives \(\frac{1}{3}\) to the internal \(4\)-vertex which are in two triangles. So \(ch^{*}(f)\)\(\geq\) 9 – 4 – \(\frac{2}{3} \times 7 – \frac{1}{3}\) = 0. When there are less than seven bad 3-vertices on \(f\), the discussion is easy. If \(V(f) \cap C_0 \neq \emptyset\), then 1 \(\leq \lvert V(f) \cap C_0 \rvert \leq\) 8 by Lemma 2.3 and the discussion is the same as above.
Suppose that \(d(f)=10\). If \(V(f) \cap C_0 = \emptyset\), by Lemma 2.4, \(f\) contains at most eight bad \(3\)-vertices. In addition, we may assume that the other two vertices are internal \(4^{-}\)-vertices. By (R2), \(ch^{*}(f)\geq 10 – 4 – \frac{2}{3} \times 8 – \frac{1}{3} \times2 = 0\). When there are less than eight bad 3-vertices on \(f\), the discussion is easy. If \(V(f) \cap C_0 \neq \emptyset\), then 1 \(\leq \lvert V(f) \cap C_0 \rvert \leq\) 9 by Lemma 2.3 and the discussion is the same as above.
Suppose that \(d(f)\geq11\). If \(f\) contains 2-vertices, then \(f\) shares two \(3^{+}\)-vertices with \(C_0\) which are not bad by definition. Then, by (R2), \(ch^{*}(f)\geq d(f) – 4 – \frac{2}{3}\times (d(f)-2)\geq 0\). So we may assume that \(f\) contains no 2-vertices. By Lemma 2.4, \(f\) contains at least two vertices which are not bad 3-vertices. It follows that \(ch^{*}(f)\geq d(f) – 4 – \frac{2}{3}\times (d(f)-2) – \frac{1}{3}\times 2 \geq 0\). ◻
Lemma 3.3. \(ch^{*}(C_0) > 0\).
Proof. We may assume that there are only \(2\)-vertices and \(3\)-vertices on \(C_{0}\) in the following. Suppose not, we can easily get that \(ch^{*}(C_0) > 0\). Then, by rough calculation using (R4), we have \(ch^{*}(C_0)\geq \lvert C_0 \rvert +4- \frac{4}{3}\lvert C_0 \rvert = \frac{1}{3} (12-\lvert C_0 \rvert)\geq\) 0 since \(|C_{0}| \leq 12\). Further, we may assume that \(|C_{0}| = 12\). Then the value of the external face \(C_{0}\) is \(0\) before the related incident internal faces give surplus value to \(C_{0}\) by (R5).
Without using the rule (R5) and under the assumptions above, the values of internal \(6^{+}\)-faces which have a common edge with \(C_{0}\) are the following.
\((a)\) The \(6\)-faces sharing one common edge with \(C_{0}\): \(6 – 4 – \frac{1}{3} \times 4 + \frac{1}{6} \times 2 = 1\) by (R2) and (R3); The 7-faces sharing one common edge with \(C_{0}\): \(7 – 4 – \frac{1}{3}\times5 = \frac{4}{3}\).
\((b)\) The 6-faces sharing two common edges with \(C_{0}\): \(6 – 4 – \frac{1}{3} \times 3 + \frac{1}{6} \times 2 – \frac{2}{3} = \frac{2}{3}\); The 7-faces sharing two common edge with \(C_{0}\): \(7 – 4- \frac{1}{3} \times 4 – \frac{2}{3} = 1\).
\((c)\) The 6-faces sharing three common edges with \(C_{0}\): \(6 – 4 – \frac{1}{3}\times 2 + \frac{1}{6} \times 2 – \frac{2}{3}\times 2\) = \(\frac{1}{3}\); The 7-faces sharing three common edges with \(C_{0}\): \(7 – 4 – \frac{1}{3}\times 3 – \frac{2}{3}\times 3 = \frac{2}{3}\).
\((d)\) The 6-faces sharing four common edges with \(C_{0}\): \(6 – 4 – \frac{2}{3}\times 3 + \frac{1}{6} \times 2 – \frac{1}{3} = 0\); The 7-faces sharing four common edges with \(C_{0}\): \(7 – 4 – \frac{2}{3}\times 3 – \frac{1}{3}\times 2 = \frac{1}{3}\).
\((e)\) By Lemma 2.3, it is impossible that a 6-face shares five common edges with \(C_{0}\). The 7-faces sharing five common edges with \(C_{0}\): \(7 – 4 – \frac{2}{3}\times 4 – \frac{1}{3} = 0\). By Lemma 2.3, it is impossible that a 7-faces share six common edges with \(C_{0}\).
\((f)\) When \(d(f)\geq 9\) and \(f\) contains at least one \(2\)-vertex, then \(f\) shares two \(3^{+}\)-vertices with \(C_0\) which are not bad by definition. Then, by (R2), \(ch^{*}(f)\geq d(f) – 4 – \frac{2}{3}\times (d(f)-2)\geq 0\).
Finally, we analyze the incident internal faces of \(C_0\) when \(\lvert C_0\rvert =12\). According to the above statements, \(ch^{*}(C_0)= 0\) is possible only when \(6\)-faces share four edges with \(C_0\) or \(7\)-faces share five edges with \(C_0\). When \(\lvert C_0 \rvert=12\), since \(C_0\) is not a bad \(12\)-cycle, it is impossible that all the incident internal faces of \(C_0\) are \(6\)-faces which sharing four edges with \(C_0\) or \(7\)-faces which sharing five edges with \(C_0\) by the assumption that there are only \(2\)-vertices or \(3\)-vertices on \(C_{0}\). So, we can always find a \(6^{+}\)-face that makes \(ch^{*}(C_0)> 0\) after (R5). ◻
The proof of Theorem 1.2 is completed by Lemmas 3.1, 3.2 and 3.3.
Mondal [6] showed that planar graphs without \(4\)-, \(5\)-, \(8\)-cycles are \(3\)-colorable. Kang et al. [4] asked that whether it is true that the planar graphs without \(4\)-, \(5\)– and \(8\)-cycles are near-bipartite. In this paper, in order to ask the question above, we prove that planar graphs without \(4\)-, \(5\)-, \(8\)-cycles and special \(6\)-cycles are near-bipartite which is a step toward their problem.
This research was partially supported by National Nature Science Foundation of China (No 12361067), Nature Science Foundation of Guangxi Province (No. 2024GXNSFAA010506) and School-level talent programs (2022KJQD04 and 2023MDKJ001).