The acyclic chromatic index of planar graphs without 4-, 6-cycles and intersecting triangles

Abstract

A proper edge k-coloring is a mapping \varphi :E\left(G\right)\to \{1,2,\dots ,k\} such that any two adjacent edges receive different colors. A proper edge k-coloring \varphi of G is called acyclic if there are no bichromatic cycles in G. The acyclic chromatic index of G, denoted by {\chi }_a^{\prime }\left(G\right), is the smallest integer k such that G is acyclically edge k-colorable. In this paper, we show that if G is a plane graph without 4-, 6-cycles and intersecting 3-cycles, \mathrm{\Delta }\left(G\right)\ge 9, then \begin{array}{c}{\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }\left(G\right)+1\hfill \end{array}.

Keywords

Acyclic edge coloring / plane graph / cycle

1 Introduction

This paper considers finite simple graphs. For a graph G, its vertex set, edge set, face set, maximum degree, minimum degree, and girth are denoted as V(G), E(G), F(G), \mathrm{\Delta }(G) (abbreviated as \mathrm{\Delta }), δ(G), and g(G), respectively. For a face f of a planar graph G, if d(f) = k (or d(f) ⩾ k, or d(f) ⩽ k), it is called a k-face (or k⁺-face, or k⁻-face). For a vertex v of a planar graph G, if d(v) = k (or d(v) ⩾ k, or d(v) ⩽ k), it is called a k-vertex (or k⁺-vertex, or k⁻-vertex). An acyclic edge coloring of a graph G is a mapping c: E(G)\to \{1,2,\dots ,k\} such that for any two adjacent edges x and y, c(x)\ne c(y), and G does not contain any bichromatic cycles. The acyclic chromatic index of G is the minimum positive integer k such that G has an acyclic edge coloring, denoted as {\chi }_a^{\prime }\left(G\right).

Fiamčík proposed a famous conjecture concerning the acyclic edge coloring of graphs.

Conjecture 1.1 [4]　For any graph G, it holds that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2.

This conjecture remains unsolved to this day. In 1991, Alon et al. [1] proved that for any graph G, {\chi }_a^{\prime }\left(G\right)\le 64\mathrm{\Delta }. In 1998, Molloy and Reed [9] proved that for any graph G, {\chi }_a^{\prime }\left(G\right)\le 16\mathrm{\Delta }. In 2020, Fialho et al. [3] proved that for any graph G, {\chi }_a^{\prime }\left(G\right)\le 3.569(\mathrm{\Delta }-1). In the same year, Kirousis and Livieratos [8] proved that for any graph G, {\chi }_a^{\prime }\left(G\right)\le 2\mathrm{\Delta }-1.

Regarding a planar graph G, Basavaraju et al. [2] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }+12. Wang et al. [15] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }+7. Wang and Zhang [13] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }+6.

For a planar graph G with g(G)⩾4, Shu et al. [12] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2. For a planar graph G with g(G)⩾5, Hou et al. [6] proved that {\chi }_a^{\prime }\left(G\right)⩽(G)+1, and when \mathrm{\Delta }(G)⩾9, {\chi }_a^{\prime }\left(G\right)=\mathrm{\Delta }(G). For a planar graph G with \mathrm{g}(G)⩾6, Hudák et al. [7] proved that if the maximum degree satisfies \mathrm{\Delta }(G)⩾6, then {\chi }_a^{\prime }\left(G\right)=\mathrm{\Delta }(G). For a planar graph G with g(G)⩾7, Wang et al. [14] proved that if the maximum degree satisfies \mathrm{\Delta }(G)⩾5, then {\chi }_a^{\prime }\left(G\right)=\mathrm{\Delta }(G). For a planar graph G with g(G)⩾8, Wang et al. [14] proved that if the maximum degree satisfies \mathrm{\Delta }(G)⩾4, then {\chi }_a^{\prime }\left(G\right)=\mathrm{\Delta }(G).

For planar graphs G without 4-cycles, Wang and Sheng [20] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+3. For planar graphs G without 4-cycles and with a maximum degree satisfying \mathrm{\Delta }(G)⩾5, Wang et al. [16] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2. For planar graphs G without 5-cycles, Shu et al. [11] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2. For planar graphs G without 4-cycles and 6-cycles, Hou et al. [5] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2.

For planar graphs G with non-adjacent 3-cycles and 3-cycles, Xie and Wu [21] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+5. For planar graphs G with non-adjacent 3-cycles and 4-cycles, Wang et al. [18] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2. For planar graphs G with non-adjacent 3-cycles and 5-cycles, Wang and Shu [17] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2. For planar graphs G with non-adjacent 3-cycles and 6-cycles, Wang et al. [19] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2.

For planar graphs G without pairwise disjoint triangles, Shu et al. [10] proved that {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+2.

This paper will prove the following theorem.

Theorem 1.1　 For planar graphs G without 4-cycles, 6-cycles, and non-intersecting 3-cycles, if \mathrm{\Delta }(G)⩾9, then {\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }(G)+1.

2 Notation

Let G be a simple planar graph. For any vertex v\in V(G),N(v) denotes the set of vertices adjacent to v, and d(v)=|N(v)|. We define N_k(v)=\{x\in N(v)\mid d(x)=k\} and n_k(v)=\left|N_k(v)\right|. If a vertex v has degree d(v) = k and is adjacent to vertex u, v is a k-neighbor of u.

For a face f\in F(G),M(v) denotes the set of faces associated with vertex v. We define M_k(v)=\{f\in M(v)\mid d(f)=k\}\text{and}{m}_k(v)=\left|M_k(v)\right|. The boundary of a face f is denoted by b(f). If u_1,u_2,\dots ,u_n are the points on the boundary of f arranged in order, then f = [u_1,u_2,\dots ,u_n]. The minimum degree of f is denoted by \delta (f)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{d\left(u_i\right),1⩽i⩽n\right\}, which represents the minimum degree among the vertices on the boundary of f.

Let c be a locally acyclic edge coloring of G. C(v)=\{c(uv):u\in N(v)\} denotes the set of colors assigned to edges incident to v. An (α, β)-bichromatic path in the coloring c is a path consisting of edges colored alternately with α and β. If the endpoint of an (α, β)-bichromatic path is vertex u and v, we denote this path as an (α, β)_{(u, v)}-bichromatic path.

3 Proof of Theorem 1.1

This paper primarily employs a technique called weight transfer to prove Theorem 1.1. Let G be a counterexample with the smallest |V(G)| + |E(G)| among all graphs satisfying the conditions of Theorem 1.1. Thus, G is a planar graph without 4-cycles and 6-cycles, and the 3-cycles do not intersect each other. Let \mathrm{\Delta }=\mathrm{\Delta }(G)⩾9, and assume that \mathrm{\Delta }=\mathrm{\Delta }(G)⩾9, {\chi }_a^{\prime }\left(G\right)\ge \mathrm{\Delta }+2. However, for any proper subgraph H of G, we have {\chi }_a^{\prime }\left(H\right)\le \mathrm{\Delta }+1. It is evident that G is a connected simple planar graph. Let C=\{1,2,\dots ,\mathrm{\Delta }+1\} be the set of colors. Next, we will investigate the structural properties of G.

3.1 Properties of minimal counterexample

Lemma 3.1　 The planar graph G is 2-connected.

Proof　Let v be an articulation point of the planar graph G, and let C_1,C_2,\dots ,C_t(t⩾2) be the connected components of G \v. For 1⩽i⩽t, there exists a non-cyclic (\mathrm{\Delta }+1)-edge coloring C_i for G_i=C_i\cup \{v\}. By adjusting C_i such that the edges associated with v are colored differently, we can obtain a coloring of G using \mathrm{\Delta }+1 colors, which contradicts the assumption. □

Lemma 3.2　 There are no 2-vertices adjacent to 3-vertices in G.

Proof　Let d(v) = 2 and N(v) = {u, w}. Suppose d(u) \le 3. We only consider the case where d(u) = 3; the case where d(u) = 2 can be proven similarly. Let N(u) = {v, u₁, u₂}. Let G^{\prime } = G − uv, and G^{\prime } has a non-cyclic (\mathrm{\Delta }+1)-edge coloring c. Let c(uu_i) = i for i = 1, 2. Consider the following two cases.

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∪C(v))| = \mathrm{\Delta }+1-3=\mathrm{\Delta }-2>0, we can assign c(uv) = α, where a\in C\(C(u)∪C(v)). In this case, G can be colored with a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which contradicts the assumption.

Case 2　|C(u)∩C(v)| = 1.

Let c(vw) = c(uu₁) = 1. If there exists \gamma \in \{3,4,\dots ,\mathrm{\Delta }+1\} such that there is no (1, γ)_{(u, v)}-bichromatic path passing through u₁ and w, we can assign c(uv) = γ, and G can be colored with a non-cyclic (\mathrm{\Delta }+1)-edge coloring, leading to a contradiction. Hence, for every \alpha \in \{3,4,\dots ,\mathrm{\Delta }+1\}, there exists a (1, α)_{(u, v)}-bichromatic path in G passing through u₁ and w. Therefore, {3,4,\dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(w), which implies C(u₁) = C(w) = {1,3,4,\dots ,\mathrm{\Delta }+1} = C \{2}. Now, we re-color the edge vw with color 2. Similarly, for every α {\in 3,4,\dots ,\mathrm{\Delta }+1}, there exists a (2, α)_{(u, v)}-bichromatic path in G passing through u₂ and w, which implies C(u₂) = {2,3,\dots ,\mathrm{\Delta }} = C \{1}. At this point, we exchange the colors of edges uu₁ and uu₂ while keeping the colors of other edges unchanged. We assign c(uv) = 3, and G can be colored with a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which contradicts the assumption. □

Lemma 3.3　 If d(v) = 2 and N(v) = {x, y}, then d(x)+d(y)⩾\mathrm{\Delta }+3.

Proof　Assume d(x) + d(x)+d(y)⩽\mathrm{\Delta }+2. Let G^{\mathrm{\prime }}=G-xv, and G^{\mathrm{\prime }} has a non-cyclic (\mathrm{\Delta }+1)-edge coloring c. Let d(x) = d + 1 and N(x)=\left\{v,x_1,x_2,\dots ,x_d\right\}. Suppose c(xx_i) = i for i=1,2,\dots ,d. Consider the following two cases.

Case 1　|C(x)∩C(v)| = 0.

Since |C \(C(x)∪C(v))| = \mathrm{\Delta } + 1 − (d(x) − 1) − (d(v) −1) = \mathrm{\Delta } + 1 − d − 1 = \mathrm{\Delta }-d\ge 1, we can assign c(xv) = α, where α \in C \(C(x)∪C(v)). Then c is a non-cyclic (\mathrm{\Delta } + 1)-edge coloring of G, which contradicts the assumption.

Case 2　|C(x)∩C(v)| = 1.

Let c(xx₁) = c(vy) = 1. Since |C \(C(x)∪C(y))| \ge \mathrm{\Delta } + 1 − (d(x) − 1) − (d(y) − 1) = \mathrm{\Delta }− (d(x) + d(y)) + 3 \ge \mathrm{\Delta } − (\mathrm{\Delta } + 2) + 3 = 1, we can assign c(xv) = β, where β \in C \(C(x)∪C(y)). Then c is a non-cyclic (\mathrm{\Delta }+1)-edge coloring of G, which contradicts the assumption. □

Lemma 3.4　 If d(v) = 3 and N(v) = {v₁, v₂, v₃}, then d(v₁) + d(v₂) + d(v₃) \ge \mathrm{\Delta } + 4.

Proof　Suppose d(v₁) + d(v₂) + d(v₃) \le \mathrm{\Delta } + 3. Since 2-degree vertices are only adjacent to vertices with 4⁺-, we have n₂(v) = 0, which implies 3\le d\left(v_{\mathbf{i}}\right)\le \mathrm{\Delta }− 3 for i = 1, 2, 3. Let G^{\prime } = G − vv₁, and G^{\prime } has a non-cyclic (\mathrm{\Delta }+1)-edge coloring c. Let c(vv₂) = 1 and c(vv₃) = 2. Consider the following three cases.

Case 1　|C(v₁)∩C(v)| = 0.

Since |C \(C(v₁)∪C(v))| = \mathrm{\Delta } + 1 − (d(v₁) − 1) − 2 = \mathrm{\Delta } + 1− d(v₁) + 1 − 2 = \mathrm{\Delta } − d(v₁) \ge 3, we can assign c(vv₁) = α, where α \in C \(C(v₁)∪C(v)). Then c is a non-cyclic (\mathrm{\Delta } + 1)-edge coloring of G, which contradicts the assumption.

Case 2　|C(v₁)∩C(v)|= 1.

Without loss of generality, assume 1\in C\left(v_1\right). Since |C \(C(v₁)∪C(v)∪C(v₂))| \ge \mathrm{\Delta } + 1 − (d(v₁) − 1) − 1 − (d(v₂) − 1) = \mathrm{\Delta } − (d(v₁) + d(v₂)) + 2 \ge \mathrm{\Delta } − \mathrm{\Delta } + 2 = 2, we can assign c(vv₁) = α, where α \in C \(C(v₁)∪C(v)∪C(v₂)). Then c is a non-cyclic (\mathrm{\Delta } + 1)-edge coloring of G, which contradicts the assumption.

Case 3　|C(v₁)∩C(v)| = 2.

Since |C \(C(v₁)∪C(v)∪C(v₂)∪C(v₃))| \ge \mathrm{\Delta } + 1 − (d(v₁) − 1) − (d(v₂) − 1) − (d(v₃) − 1) = \mathrm{\Delta }− (d(v₁) + d(v₂) + d(v₃)) + 4 \ge 1, we can assign c(vv₁) = α, where α \in C \(C(v₁)∪C(v)∪C(v₂)∪C(v₃)). Then c is a non-cyclic (\mathrm{\Delta }+1)-edge coloring of G, which contradicts the assumption. □

Lemma 3.5　 If d(v) \ge 4, then n₂(v) \le d(v) − 2.

Proof　Let d(v) = d and N(v) = {u,v_1,v_2,\dots ,v_{(d-1)}}. Let d(u) = d(v_i) = 2, N(u) = {v, u₁}, and N(v_i) = {v,v_i^{\prime }}(i=1,2,\cdots ,d-2). Let G^{\prime } = G − uv, and G^{\prime } has a non-cyclic (\mathrm{\Delta }+1)-edge coloring c. Suppose c(vv_i) = i (i=1,2,\dots ,d-1). Consider the following two cases:

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∪C(v))| = \mathrm{\Delta } + 1 − 1 − (d − 1) = \mathrm{\Delta } − d + 1 \ge 1, we can assign c(uv) = α, where α \in C \(C(u)∪C(v)). Then c is a non-cyclic (\mathrm{\Delta }+1)-edge coloring of G, which contradicts the assumption.

Case 2　|C(u)∩C(v)| = 1.

When c(uu₁) \in {1, 2, \dots , d−2}, assume c(uu₁) = 1. Since |C \(C(u)∪C(v)∪C(v₁))| \ge \mathrm{\Delta } + 1 − 1 − (d − 2) − 1 = \mathrm{\Delta }− d + 1 \ge 1, we can assign c(uv) = α, where α \in C \(C(u)∪C(v)∪C(v₁)). Then c is a non-cyclic (\mathrm{\Delta }+1)-edge coloring of G, which contradicts the assumption.

When c(uu₁)=c(vv_(d−1))=d−1, if there exists γ \in {d, d+1, \dots ,\mathrm{\Delta }+1} such that there is no (d−1, γ)-bichromatic path in G passing through u₁ and v_(d−1), we can assign c(uv) = γ, and G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, for every α \in {d, d+1, \dots ,\mathrm{\Delta }+1}, there exists a (d−1, α)-bichromatic path in G passing through u₁ and v_(d-1). Thus, {d, d+1, \dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(v_(d−1)). Since d(u₁) \le \mathrm{\Delta }, there must exist i₀ \in {1, 2, \dots , d−2} such that i₀ \in C(u₁). In this case, we can re-color the edge uu₁ with i₀, and assign \beta \in \{d,d+1,\dots ,\mathrm{\Delta }+1\}\\{c(v_{i_0}{v}_{i_0}^{\prime })\} to uv. Then G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. □

Lemma 3.6　 If f = [uvw] and d(v) = 2, then d(u) \ge 5 and d(w) \ge 5.

Proof　Suppose d(u) \le 4, without loss of generality, let d(u) = 4 and N(u)={v,w,u₁,u₂}. Let G^{\prime } = G − uv, and G^{\prime } has a non-cyclic (\mathrm{\Delta }+1)-edge coloring c. Assume c(vw) = 1 and c(uw) = 2. Consider the following two cases.

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∪C(v))| = \mathrm{\Delta } + 1 − 3 − 1 = \mathrm{\Delta } − 3 > 0, we can assign c(uv) = α, where α \in C \(C(u)∪C(v)), and c becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction.

Case 2　|C(u)∩C(v)| = 1.

Assume c(uu₁) = c(vw) = 1 and c(uu₂) = 3. If there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that there is no (1, γ)_{(u, v)}-bichromatic path passing through u₁ and w in G, we can assign c(uv) = γ, and G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, there exists a (1, α)_{(u, v)}-bichromatic path passing through u₁ and w in G. Thus, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(w). Since d(w) \le \mathrm{\Delta } and d(u₁) \le \mathrm{\Delta }, it follows that C(w) = {1, 2, 4, 5, \dots ,\mathrm{\Delta }+1} = C \{3}, and {2, 3} \ C(u₁) ≠ Ø. By recoloring vw with 3, c remains a non-cyclic (\mathrm{\Delta } + 1)-edge coloring of G − uv. Similarly, for every α \in \{4,5,\dots ,\mathrm{\Delta }+1\}, there exists a (3, α)_{(u, v)}-bichromatic path passing through u₂ and w in G. Thus, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(u₂)∩C(w). Since d(u₂) \le \mathrm{\Delta }, it follows that {1, 2} \ C(u₂) ≠ Ø.

If 3 \in C(u₁) and 2 \in C(u₂), we can recolor uu₁ with 3, uu₂ with 2, uw with 1, vw with 3, and uv with 4. G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction.

If 3 \in C(u₁) and 1 \in C(u₂), we can recolor uu₁ with 3, uu₂ with 1, and uv with 4. G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction.

If 2 \in C(u₁) and 2 \in C(u₂), if there is no (2, 4)_{(u, v)}-bichromatic path passing through u₁ and w in G, we can recolor uu₁ with 2, uw with 1, vw with 2, and uv with 4. G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, there must exist a (2, 4)_{(u, v)}-bichromatic path passing through u₁ and w in G. In this case, we can recolor uu₂ with 2, uw with 3, vw with 2. Since G must contain a (2, 4)_{(u, v)}-bichromatic path passing through u₁ and w, there is no (2, 4)_{(u, v)}-bichromatic path passing through u₂ and w in G. We can then recolor uv with 4. G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction.

If 2 \in C(u₁) and 1 \in C(u₂), we can recolor uu1 with 2, vw with 1, uu₂ with 1, uw with 3, and uv with 4. G becomes a non-cyclic (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. □

Lemma 3.7　 Let f = [uvw], if d(v) = 3, then d(u) \ge 4 and d(w) \ge 4.

Proof　Assume d(u) = 3, N(u) = {v, w, u₁}, and N(v) = {u, w, v₁}. Let G^{\prime } = G − uv. G^{\prime } has a cycle-free (\mathrm{\Delta }+1)-edge coloring c. We consider the following three cases.

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∩C(v))| = \mathrm{\Delta }+1 − 2 − 2 = \mathrm{\Delta }-3>0, we can choose α \in C \(C(u) ∪ C(v)) such that c(uv) = α. Thus, c is a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction.

Case 2　|C(u) ∩ C(v)| = 1.

Case 2.1　 c(vw) = c(uu₁) = 1.

Without loss of generality, assume c(vv₁) = 3. If there exists γ \in {4,5,\dots ,\mathrm{\Delta }+1} such that G does not contain a (1, γ)_{(u, v)}-bicolor path through u₁ and w, we can set c(uv) = γ, and G would have a cycle-free (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Hence, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G contains a (1, α)_{(u, v)}-bicolor path through u₁ and w. Therefore, {4,5,\dots ,\mathrm{\Delta }+1} ⊆ C(u, 1) ∩ C(w). Since d(w) ⩽\mathrm{\Delta }, we have C(w) = {1,2,4,5,\dots ,\mathrm{\Delta }+1} = C \{3}. If G does not contain a (1, 3)_{(u, w)}-bicolor path through u₁ and v₁, we can color uw with 3 and uv with 2, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction. Hence, G must contain a (1, 3)_{(u, w)}-bicolor path through u₁ and v₁. Thus, 3 \in C(u₁) and 1 \in C(v₁). Based on the above discussion, we can conclude that C(u₁) = {1,3,4,5,\dots ,\mathrm{\Delta }+1} = C \{2}. If {4,5,\dots ,\mathrm{\Delta }+1}\C(v₁) ≠ Ø, we can choose β \in {4,5,\dots ,\mathrm{\Delta }+1}\C(v₁) and recolor vv₁ with β. Then, we can color uv with 3, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction. Therefore, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(v₁), which implies C(v₁) = {1,3,4,5,\dots ,\mathrm{\Delta }+1} = C \{2}. In this case, we can recolor vv₁ with 2 and color uv with 3, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction.

Case 2.2　 c(vv₁) = c(uw) = 2.

Suppose c(vw) = 3. If there exists γ \in {4,5,\dots ,\mathrm{\Delta }+1} such that there is no (2, γ)_{(u, v)}-bicolor path through v₁ and w in G, we can set c(uv) = γ, and G would have a cycle-free (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, for every α \in {4,5,\dots ,\mathrm{\Delta }+1}, there exists a (2, α)_{(u, v)}-bicolor path through v₁ and w in G. This implies that {4,5,\dots ,\mathrm{\Delta }+1} ⊆ C(v₁) ∩ C(w). Since d(w) ⩽\mathrm{\Delta }, we have C(w) = {\dots ,\mathrm{\Delta }+1} = C \{1}. If G does not contain a (1, 2)_{(v, w)}-bicolor path through v₁ and u₁, we can color vw with 1, uv with 3, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction. Hence, G must contain a (1, 2)_{(v, w)}-bicolor path through v₁ and u₁. Thus, 1 \in C(v₁) and 2\in C(u₁). Based on the above discussion, we can conclude that C(v₁) = {1,2,4,5,\dots ,\mathrm{\Delta }+1} = C \{3}. Since d(u₁) ⩽\mathrm{\Delta }, from the previous discussion, we have {3,4,\dots ,\mathrm{\Delta }+1}\C(u₁) ≠ Ø. In this case, we can choose β \in {3,4,\dots ,\mathrm{\Delta }+1}\C(u₁) and recolor uu₁ with β. Then, we can color uv with 1, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction.

Case 2.3　 c(vv₁) = c(uu₁) = 1.

Suppose c(vw) = 3. If there exists γ \in {4,5,\dots ,\mathrm{\Delta }+1} such that there is no (1, γ)_{(u, v)}-bicolor path through v₁ and u₁ in G, we can set c(uv) = γ, and G would have a cycle-free (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, for every α \in {4,5,\dots ,\mathrm{\Delta }+1}, there exists a (1, α)_{(u, v)}-bicolor path through v₁ and u₁ in G. This implies that {4,5,\dots ,\mathrm{\Delta }+1}⊆C(v₁)∩C(u₁). Since d(v₁) ⩽\mathrm{\Delta } and d(u₁) ⩽\mathrm{\Delta }, we have {2, 3}\C(v₁) ≠ Ø and {2, 3}\C(u₁) ≠ Ø. If 2 \in C(v₁), we can recolor vv₁ with 2, which is similar to the discussion in Case 2.2. This would result in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction. Hence, 2 \in C(v₁), and we have C(v₁) = {1,2,4,5,\dots ,\mathrm{\Delta }+1} = C \{3}. If 3 \in C(u₁), we can recolor uu₁ with 3, which is similar to the discussion in Case 2.1. This would result in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction. Thus, 3 \in C(u₁), and we have C(u₁) = {1,3,4,\dots ,\mathrm{\Delta }+1} = C \{2}. Since d(w) ⩽\mathrm{\Delta }, we have {1,4,5,\dots ,\mathrm{\Delta }+1}\C(w) ≠ Ø. If 1 \in C(w), we can recolor vw with 1, vv₁ with 3, and uv with 4, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction. Therefore, 1 \in C(w), and there must exist β \in {4,5,\dots ,\mathrm{\Delta }+1}\C(w). In this case, we can recolor vw with β, uv with 3, resulting in a cycle-free (\mathrm{\Delta }+1)-edge coloring of G, which is a contradiction.

□

Case 3　|C(u)∩C(v)| = 2.

In this case, c(uu₁) = c(vw) = 1, and c(uw) = c(vv₁) = 2. If there exists γ \in {3, 4, \dots ,\mathrm{\Delta }+1} such that there is no (1, γ)_{(u, v)}-bicolor path through u₁ and w and no (2, γ )_{(u, v)}-bicolor path through v₁ and w in G, we can set c(uv) = γ, and G would have a cycle-free (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, for every α \in {3, 4, \dots ,\mathrm{\Delta }+1}, either there exists a (1, α)_{(u, v)}-bicolor path or there exists a (2, α)_{(u, v)}-bicolor path in G. This implies that {3, 4, \dots ,\mathrm{\Delta }+1} ⊆ C(w), which means C(w) = {1, 2, 3, \dots ,\mathrm{\Delta }+1}. However, this contradicts the fact that d(w) ⩽\mathrm{\Delta }, as in this case, d(w) = \mathrm{\Delta }+1.

Lemma 3.8　 If d(v) = 4 and n₂(v) = 2, then vertex v is not incident to any triangular face.

Proof　Suppose vertex v is incident to a triangular face f = [uvw], according to Lemma 3.6, both u and w are 3⁺-vertices. Let N(v) = {u, x, y, w}, where d(x) = d(y) = 2. N(x) = {v, x₁}, and N(y) = {v, y₁}. Let G^{\prime } = G − vx, and G^{\prime } has a cycle-free (\mathrm{\Delta }+1)-edge coloring c. Assume c(vy) = 1, c(vw) = 2, and c(uv) = 3. Consider the following two cases:

Case 1　|C(v)∩C(x)| = 0.

Since |C \(C(v)∪C(x))| = \mathrm{\Delta }+1 − 3 − 1 = \mathrm{\Delta }-3>0, we can assign c(vx) = α, where α \in C \(C(v)∪C(x)). Thus, c forms a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2　|C(v)∩C(x)| = 1.

Case 2.1　 c(xx₁) = c(vy) = 1.

Since |C \(C(v)∪C(x)∪C(y))| \ge \mathrm{\Delta }+1 − 3 − 1 = \mathrm{\Delta }-3>0, we can assign c(vx) = α, where α \in C \(C(v)∪C(x)∪C(y)). Thus, c forms a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2.2　 c(xx₁) \in {2, 3}.

Without loss of generality, assume c(xx₁) = c(vw) = 2. If there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that G does not contain a (2, γ)_{(v, x)}-bicolor path passing through x₁ and w, we can assign c(vx) = γ, and G would have a cycle-free (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Therefore, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G must contain a (2, α)_{(v, x)}-bicolor path passing through x₁ and w. Thus, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(x₁)∩C(w). Since d(x₁) ⩽\mathrm{\Delta } and d(w) ⩽\mathrm{\Delta }, we have {1, 3}\C(x₁) ≠ Ø and {1, 3}\C(w) ≠ Ø. If 1 \in C(x₁), we can assign weight 1 to xx₁ and choose β \in {4, 5, \dots ,\mathrm{\Delta }+1}\{c(yy₁)} to color vx. Thus, c forms a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. Therefore, 1 \in C(x₁) and 3 \in C(x₁). Now, we assign weight 3 to xx₁, and c remains a cycle-free (\mathrm{\Delta }+1)-edge coloring for G − vx. If there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that G does not contain a (3, γ)_{(v, x)}-bicolor path passing through x₁ and u, we can assign c(vx) = γ, and G would have a cycle-free (\mathrm{\Delta }+1)-edge coloring, which is a contradiction. Thus, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G must contain a (3, α)_{(v, x)}-bicolor path passing through x₁ and u. Hence, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(x1)∩C(u), and since d(u) ⩽\mathrm{\Delta }, we have {1, 2}\C(u) ≠ Ø.

Case 2.2.1　 c(uw) = β \in {4, 5, \dots ,\mathrm{\Delta }+1}.

From the above discussion, it can be concluded that there exists a (2,\beta {)}_{(v,x_1)}-bicolor path passing through x₁ and w in G − vx. Therefore, 2 \in C(u), implying that C(u) = {2, 3, 4, \dots ,\mathrm{\Delta }+1} = C \ {1}. Similarly, there exists a (3,\beta {)}_{(v,x_1)}-bicolor path passing through x₁ and u in G − vx, which implies 3 \in C(w), i.e., C(w) = {2, 3, 4, \dots ,\mathrm{\Delta }+1} = C \ {1}. Hence, there is no (3, 1)_{(v, x)}-bicolor path passing through x₁ and u in G−vx.

Let \varphi(vx) = 1, remove the color of vy, and let \varphi(e) = c(e) for e \in E(G) \ {vx, vy}. Then \varphi is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G − vy. When |\varphi(v)∩\varphi(y)| = 0, since |\varphi(v)∪\varphi(y)| = 3 + 1 = 4 < \mathrm{\Delta }+1, we can let \varphi(vy) = β, where β \in {4, 5, \dots ,\mathrm{\Delta }+1} \ {\varphi(yy₁)}, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. When |\varphi(v)∩\varphi(y)| = 1, if \varphi(yy₁) = 1, we can let \varphi(vy) = 4, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. If \varphi(yy₁) = \varphi(vw) = 2, from the above discussion, it can be inferred that for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, there exists a (2, α)_{(v, x)}-bicolor path passing through x₁ and w in G − vx. Therefore, there is no (2, α)_{(v, y)}-bicolor path passing through y₁ and w in G − vy. We can let \varphi(vy) = α, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. If \varphi(yy₁) = \varphi(vu) = 3, from the above discussion, it can be inferred that for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, there exists a (3, α)_{(v, x)}-bicolor path passing through x₁ and u in G − vx. Therefore, there is no (3, α)_{(v, y)}-bicolor path passing through y₁ and u in G − vy. We can let \varphi(vy) = α, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2.2.2　 c(uw) = 1.

In this case, let c(vx) = 1, remove the color of vy without changing the colors of other edges. The resulting edge coloring \varphi is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G − vy. When |\varphi(v)∩\varphi(y)| = 0, since |\varphi(v)∪\varphi(y)| = 3 + 1 = 4 < \mathrm{\Delta }+1, we can let \varphi(vy) = β, where β \in {4, 5, \dots ,\mathrm{\Delta }+1} \ {\varphi(yy₁)}, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. When |\varphi(v)∩\varphi(y)| = 1, if \varphi(yy₁) = 1, we can let \varphi(vy) = 4, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. If \varphi(yy₁) = \varphi(vw) = 2, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, it can be inferred from the previous discussion that there exists a (2, α)_{(v, x)}-bicolor path passing through x₁ and w in G − vx. Therefore, there is no (2, α)_{(v, y)}-bicolor path passing through y₁ and w in G − vy for \varphi. We can let \varphi(vy) = α, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. If \varphi(yy₁) = \varphi(vu) = 3, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, it can be inferred from the previous discussion that there exists a (3, α)_{(v, x)}-bicolor path passing through x₁ and u in G − vx. Therefore, there is no (3, α)_{(v, y)}-bicolor path passing through y₁ and u in G −vy for \varphi. We can let \varphi(vy) = α, and \varphi becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. □

Lemma 3.9　 If d(v) = 4 and n₂(v) = 2, then n₃(v) = 0.

Proof　According to Lemma 3.8, vertex v is incident to either a 5-face or a 7⁺-face. Let’s assume n₃(v) \ge 1. We denote N(v) = {u, v₁, v₂, v₃}, where d(u) = d(v₁) = 2, d(v₂) = 3, N(u) = {v, u₁}, N(v₂)={v,v_2^{\prime },v_1^{″}}, and N(v₂)={v,v_2^{\prime },v_1^{″}}. Let G^{\prime } = G − uv, and G^{\prime } has a cycle-free (\mathrm{\Delta }+1)-edge coloring c. Assuming c(vv_i) = i (i = 1, 2, 3), we consider the following two cases:

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∪C(v))| = \mathrm{\Delta }+1 − 1 − 3 = \mathrm{\Delta }-3>0, we can let c(uv) = α, where α \in C \(C(u)∪C(v)). Thus, c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2　|C(u)∩C(v)| = 1.

When c(uu₁) = c(vv₁) = 1, due to |C \(C(u)∪C(v)∪C(v₁))| \ge \mathrm{\Delta }+1 − 3 − 1 = \mathrm{\Delta }-3>0, we can let c(uv) = α, where α \in C \(C(u)∪C(v)∪C(v₁)). Thus, c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

When c(uu₁) = c(vv₂) = 2, due to |C \(C(u)∪C(v)∪C(v₂))| \ge \mathrm{\Delta }+1 − 3 − 2 = \mathrm{\Delta }-4>0, we can let c(uv) = α, where α \in C \(C(u)∪C(v)∪C(v₂)). Thus, c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

When c(uu₁) = c(vv₃) = 3, if there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that G does not have a (3, γ)_(u,v)-bicolor path passing through u₁ and v₃, we can let c(uv) = γ, and c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. Therefore, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G has a (3,α)_(u,v)-bicolor path passing through u₁ and v₃. Hence, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(v₃). Since d(u₁) ⩽\mathrm{\Delta }, we have {1, 2}\C(u₁) ≠ Ø. If 1 \in C(u₁), we can monochromatically color uu₁ with 1 and use \beta \in \{4,5,\dots ,\mathrm{\Delta }+1\}\mathrm{\setminus }\{c\left(v_1{v}_1^{\prime }\right)to color uv. This results in a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. If 2 \in C(u₁), we can bichromatically color uu₁ with 2 and use \beta \in \{4,5,\dots ,\mathrm{\Delta }+1\}\mathrm{\setminus }\{c\left(v_2{v}_2^{\prime }\right),c\left(v_2{v}_2^{″}\right)\}to color uv. This also leads to a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. □

Lemma 3.10　 If d(v) = 4, f is a 3-face associated with vertex v, and δ(f) = 3, then n₂(v) = 0.

Proof　We assume n₂(v) \ge 1. Let N(v) = {u,v₁,v₂,v₃}, and let f = [vv₁v₂]. We have d(u) = 2, d(v₁) = 3, N(u) = {v, u₁}, and N(v₁)={v,v₂,v_1^{\prime }}. Let G^{\prime } = G − uv, and G^{\prime } has a cycle-free (\mathrm{\Delta }+1)-edge coloring c. Assuming c(vv_i) = i (i = 1, 2, 3), we consider the following two cases.

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∪C(v))| = \mathrm{\Delta }+1 − 1 − 3 = \mathrm{\Delta }-3>0, we can let c(uv) = α, where α \in C \(C(u)∪C(v)). Thus, c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2　|C(u)∩C(v)| = 1.

Case 2.1　 c(uu₁) = c(vv₁) = 1.

Since |C \(C(u)∪C(v)∪C(v₁))| ⩾\mathrm{\Delta }+1-3-2=\mathrm{\Delta }-4>0, we can let c(uv) = α, where α \in C \(C(u)∪C(v)∪C(v₁)). Thus, c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2.2　 c(uu₁) = c(vv₂) = 2.

If there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that G does not have a (2,γ)_(u,v)-bicolor path passing through u₁ and v₂, we can let c(uv) = γ, and c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. Therefore, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G has a (2,α)_(u,v)-bicolor path passing through u₁ and v₂. Hence, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(v₂). Since d(u₁) ⩽\mathrm{\Delta } and d(v₂) ⩽\mathrm{\Delta }, we have {1, 3}\C(u₁) ≠ Ø and {1, 3}\C(v₂) ≠ Ø.

If 1 \in C(u₁), we can monochromatically color uu₁ with 1 and use β \in {4,5,\dots ,\mathrm{\Delta }+1}\{c(v_1{v}_1^{\prime }), c(v₁v₂)} to color uv. This results in a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. Thus, 1 \in C(u₁).

Since 3 \in C(u₁), we can bichromatically color uu₁ with 3 without changing the colors of other edges. In this case, c remains a cycle-free (\mathrm{\Delta }+1)-edge coloring for G − uv. If there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that G does not have a (3, γ)_(u,v)-bicolor path passing through u₁ and v₃, we can let c(uv) = γ, and c becomes a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. Therefore, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G has a (3, α)_(u,v)-bicolor path passing through u₁ and v₃. Hence, {4, 5, \dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(v₃). Since d(v₃) ⩽\mathrm{\Delta }, we have {1, 2}\C(v₃) ≠ Ø.

Case 2.2.1　 c(v₁v₂) = β \in {4, 5, \dots ,\mathrm{\Delta }+1}.

Assume c(v₁v₂)= β = 4. From the above discussion, we know that there exists a (2, 4)_(u,v)-bicolor path P in G−uv passing through u₁ and v₂, which includes v_1{v}_1^{\prime }. Therefore, c(v_1{v}_1^{\prime })=2. If 3 \in C(v₂) and 2 \in C(v₃), we can color vv₂ with weight 3, vv₃ with weight 2, and vu with weight 4. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 3 \in C(v₂) and 1 \in C(v₃), we can color vv₂ with weight 3, vv₃ with weight 1, vv₁ with weight 4 using γ \in {2,5,6,\dots ,\mathrm{\Delta }+1}\{c(v_1{v}_1^{\prime })}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 1 \in C(v₂) and 2 \in C(v₃), we can color vv₂ with weight 1, vu with weight 2, and vv₁ with weight γ \in {5,6,\dots ,\mathrm{\Delta }+1}\{c(v_1{v}_1^{\prime })}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 1 \in C(v₂) and 1 \in C(v₃), we can color v₁v₂ with weight 1, vu with weight 1, and vv1 with weight γ \in {4,5,\dots ,\mathrm{\Delta }+1}\{c(v_1{v}_1^{\prime })}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction.

Case 2.2.2　 c(v₁v₂) = 3, which means c(v₂) = C \{1}.

If 2 \in C(v₃), we can color vv₂ with weight 1, vu with weight 2, and vv₁ with weight γ \in {4, 5, \dots , +1}{c(v_1{v}_1^{\prime })}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 1 \in C(v₃), we can color vv₁ with weight γ \in{4, 5, \dots ,\mathrm{\Delta }+1}\{c(v_1{v}_1^{\prime })} and vu with weight 1. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction.

Case 2.3　 c(uu₁) = c(vv₃) = 3.

If there exists γ \in {4, 5, \dots ,\mathrm{\Delta }+1} such that G does not have a (3, γ)_(u,v)-bicolor path passing through u₁ and v₃, we can let c(uv) = γ, and c remains a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction. Therefore, for every α \in {4, 5, \dots ,\mathrm{\Delta }+1}, G has a (3, α)_(u,v)-bicolor path passing through u₁ and v₃. Hence, {4,5,\dots ,\mathrm{\Delta }+1} ⊆ C(u₁)∩C(v₃). Since d(u₁) ⩽\mathrm{\Delta }, we have {1, 2}\C(u₁) ≠ Ø. If 1 \in C(u₁), we can color uu1 with weight 1 and uv with weight β \in {4, 5, \dots ,\mathrm{\Delta }+1}\{c(v_1{v}_1^{\prime }),c(v₁v₂)}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 2 \in C(u₁), the discussion is similar to Case 2.2, and we can conclude that G is cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction.

Lemma 3.11　 If d(v) = 5 and n₂(v) = 3, then vertex v is not incident with a 2-path in the same 3-face.

Proof　Suppose vertex v is incident with a 2-neighbor u in the 3-face f = [uvw]. Let N(v) = {u, x, y, z, w}, d(x) = d(y) = 2, N(x) = {v, x₁}, N(y) = {v, y₁}, and N(u) = {v, w}. Let G^{\prime } = G − uv. G^{\prime } has a cycle-free (\mathrm{\Delta }+1)-edge coloring c. Suppose c(vx) = 1, c(vy) = 2, c(vz) = 3, and c(vw) = 4. Consider the following two cases.

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u) ∪ C(v))| = \mathrm{\Delta }+1 − 4 − 1 = \mathrm{\Delta }-4>0, we can assign c(uv) = α, where α \in C \(C(u) ∪ C(v)). Thus, c is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2　|C(u)∩C(v)| = 1.

When c(uw) = c(vx) = 1, since |C \(C(u)∪C(v)∪C(x))| \ge \mathrm{\Delta }+1 − 4 − 1 = \mathrm{\Delta }-4>0, we can assign c(uv) = α, where α \in C \(∪C(x)). Thus, c is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

When c(uw) = c(vy) = 2, since |C \(C(u)∪C(v)∪C(y))| \ge \mathrm{\Delta }+1 − 4 − 1 = \mathrm{\Delta }-4>0, we can assign c(uv) = α, where α \in C \(C(u)∪C(v)∪C(y)). Thus, c is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

When c(uw) = c(vz) = 3, if there exists γ \in {5, 6, \dots ,\mathrm{\Delta }+1} such that G does not have a (3,γ)_(u,v)-bicolor path passing through z and w, we can assign c(uv) = γ. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. Therefore, for every α \in {5, 6, \dots ,\mathrm{\Delta }+1}, G has a (3, α)_(u,v)-bicolor path passing through z and w. Hence, {5, 6, \dots ,\mathrm{\Delta }+1} ⊆ C(z) ∩ C(w). Since d(w) ⩽\mathrm{\Delta }, we have {1, 2}\C(w) ≠ Ø. If 1 \in C(w), we can color uw with weight 1 and uv with β \in {5, 6, \dots ,\mathrm{\Delta }+1}\{c(xx₁)}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 2 \in C(w), we can color uw with weight 2 and uv with β \in {5, 6, \dots ,\mathrm{\Delta }+1}\{c(yy₁)}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction.

Lemma 2.12　 If d(v) = 5, f is a 3-face incident with vertex v, and δ(f) = 3, then n₂(v) \le 2.

Proof　Suppose n₂(v) \ge 3. Let N(v) = {u, v₁, v₂, v₃, v₄}, and f = [vv₃v₄]. We have d(u) = d(v₁) = d(v₂) = 2 and d(v₄) = 3. Let N(u) = {v, u₁}, N(v_i) = {v, v_i^{\prime }\}(i = 1,2), and N(v₄)={v, v₃, v_4^{\prime }}. Let G^{\prime } = G − uv, and G^{\prime } has a cycle-free (\mathrm{\Delta }+1)-edge coloring c. Assume c(vv_i) = i (i = 1, 2, 3, 4). Consider the following two cases:

Case 1　|C(u)∩C(v)| = 0.

Since |C \(C(u)∩C(v))| = \mathrm{\Delta }+1 − 4 − 1 = \mathrm{\Delta }-4>0, we can assign c(uv) = α, where α \in C \(C(u)∩C(v)). Thus, c is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

Case 2　|C(u) ∩ C(v)| = 1.

When c(uu₁) = i \in {1, 2, 4}, since |C \(C(u)∪C(v)∪C(v_i))| \ge \mathrm{\Delta }+1 − 4 − 2 = \mathrm{\Delta }-5>0, we can assign c(uv) = α_i, where α_i \in C \(C(u)∪ C(v) ∪ C(v_i)) (i = 1, 2, 4). Thus, c is a cycle-free (\mathrm{\Delta }+1)-edge coloring for G, which is a contradiction.

When c(uu₁) = c(vv₃) = 3, if there exists γ \in {5, 6, \dots ,\mathrm{\Delta }+1} such that G does not have a (3, γ)_(u,v)-bicolor path passing through u₁ and v₃, we can assign c(uv) = γ. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. Therefore, for every α \in {5, 6, \dots ,\mathrm{\Delta }+1}, G has a (3, α)_(u,v)-bicolor path passing through u₁ and v₃. Hence, {5, 6, \dots ,\mathrm{\Delta }+1} ⊆ C(u₁) ∩ C(v₃). Since d(u₁) ⩽\mathrm{\Delta }, we have {1, 2, 4}\C(u₁) ≠ Ø. If 1 \in C(u₁), we can color uu₁ with weight 1 and uv with β \in {5, 6, \dots ,\mathrm{\Delta }+1}\{c(v₂v_2^{\prime })}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 2 \in C(u₁), we can color uu₁ with weight 2 and uv with β\in{5, 6, \dots ,\mathrm{\Delta }+1}\{c(v₂v_2^{\prime })}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction. If 4 \in C(u₁), we can color uu₁ with weight 4 and uv with β \in {5, 6, \dots ,\mathrm{\Delta }+1}\{c(v₄v_4^{\prime }), c(v₃v₄)}. G becomes cycle-free and can be colored with (\mathrm{\Delta }+1) colors, which is a contradiction.

3.2 Weight transfer

Since G satisfies the property of having no 4-cycles or 6-cycles, and 3-cycles do not intersect with each other, \mathrm{\Delta }(G) = \mathrm{\Delta }\ge 9, the following conclusions hold:

(P1) If d(f) = 3, then all faces adjacent to f are 7⁺-faces.

(P2) If d(f) = 3 and δ(f) = 2, then f is adjacent to at least one 8⁺-face.

(P3) If d(f) = 5, then the faces adjacent to f are either 5-faces or 7⁺-faces.

(P4) If d(f) = 5 and δ(f) = 2, then f is adjacent to at least one 7⁺-face.

(P5) If a vertex v is incident with a 3-face, n₂(v) ≠ 0, and v’s 2-neighbor is incident with a 3-face, then when 1 \le n₂(v) \le 3, m_{7^{+}}(v) \ge 2, and there is at least one 8⁺-face among them. When 4 \le n₂(v) \le d(v) − 2, if n₂(v) is odd, then m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+1}{2}, and there is at least one 8+-face among them; if n₂(v) is even, then m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+2}{2}, and there is at least one 8⁺-face among them.

(P6) If a vertex v is incident with a 3-face, n₂(v) ≠ 0, and v’s 2-neighbor is not incident with a 3-face, then when 1 \le n₂(v) \le 2, m_{7^{+}}(v) \ge 2. When 3 \le n₂(v) \le d(v) − 2, if n₂(v) is odd, then m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+3}{2}; if n₂(v) is even, then m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+2}{2}.

(P7) If a vertex v is not incident with a 3-face, n₂(v) ≠ 0, then when n₂(v) is odd, m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+1}{2}; when n₂(v) is even, m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)}{2}.

According to Euler’s formula for connected planar graphs |V|+|F|-|E\mid =2 and the sum of degrees formula \sum _{v\in V\left(G\right)} d\left(v\right)=\sum _{f\in F\left(G\right)} d\left(f\right)=2\left|E\right(G\left)\right|, we have

\sum _{v\in V\left(G\right)}\left(\frac{3}{2}d\left(v\right)-5\right)+\sum _{f\in F\left(G\right)}(d(f)-5)=-10.

Now we construct a weight function ω such that when v \in V(G), \omega \left(v\right)=\frac{3}{2}d\left(v\right)-5, and when f \in F(G), ω(f) = d(f) − 5. It follows that {\sum }_{(x\in V(G)\cup F(G))} ω(x) = −10. Based on the structural properties of G, we will perform weight transfers on the vertices and faces of G according to the following rules, while maintaining the total weight sum unchanged, resulting in a new weight function {\omega }^{\mathrm{\prime }}(x). We will prove that for any x \in V(G)∪F(G), {\omega }^{\mathrm{\prime }}(x) \ge 0. This will lead to a contradiction:

0\le \sum _{x\in V\left(G\right)\cup F\left(G\right)} {\omega }^{\prime }\left(x\right)=\sum _{x\in V\left(G\right)\cup F\left(G\right)}\omega \left(x\right)=-10.

This contradiction shows that G does not exist, thus establishing the validity of Theorem 1.1.

Weight transfer rules:

(R1) Each 7+-face f transfers weight \frac{d\left(f\right)-5}{d\left(f\right)} to each of its vertices.

(R2) For each 4-vertex v, transfer weight \frac{9}{14} to adjacent 2-vertices and weight \frac{1}{8} to adjacent 3-vertices;

For each 5-vertex v, transfer weight \frac{11}{14} to adjacent 2-vertices and weight \frac{1}{4} to adjacent 3-vertices;

For each 6-vertex v, transfer weight \frac{195}{224} to adjacent 2-vertices and weight \frac{3}{8} to adjacent 3-vertices;

For each 7-vertex v, transfer weight \frac{277}{280} to adjacent 2-vertices;

For each 8⁺-vertex v, transfer weight \frac{93}{84} to adjacent 2-vertices.

(R3) Each 7⁺-vertex v transfers weight \frac{1}{2} to adjacent 3-vertices.

(R4) For each 4⁺-vertex v associated with a 3-face f, if δ(f) \le 3, v transfers weight 1 to f; if δ(f) \ge 4, v transfers weight \frac{2}{3} to f.

Next, we will verify that ∀v \in V(G), ω'(v) \ge 0. According to Lemma 3.1, δ(G) \ge 2.

(1) d(v) = 2, ω(v) = −2.

Let N(v) = {x, y}. According to Lemma 3.2 and Lemma 3.3, both x and y are 4⁺-vertices, and d(x) + d(y)\ge \mathrm{\Delta } + 3 \ge 12.

When vertex v is associated with a 3-face, according to Lemma 3.6 and (P₂), x and y are both 5⁺-vertices and m₈+(v) = 1. Based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge -2+\frac{3}{8}+\mathrm{m}\mathrm{i}\mathrm{n}\{\frac{11}{14}+\frac{277}{280},2\times \frac{195}{224}\}>0.

When vertex v is not associated with a 3-face, according to (P₄), m_{7^{+}}(v) \ge 1. Based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge -2+\frac{2}{7}+\mathrm{m}\mathrm{i}\mathrm{n}\{\frac{9}{14}+\frac{93}{84},\frac{11}{14}+\frac{277}{280},2\times \frac{195}{224}\}>0.

(2) d(v)=3, ω(v)=-\frac{1}{2}.

Let N(v) = {x, y, z}. According to Lemma 3.2 and Lemma 3.4, x, y, and z are all 3⁺-vertices, and d(x) + d(y) + d(z) \ge \mathrm{\Delta }+4\ge 13.

When vertex v is associated with a 3-face f = [xyv], according to Lemma 3.7, x and y are both 4⁺-vertices, i.e., n₃(v) \le 1. According to (P1), m_{7^{+}}(v) \ge 2. If n₃(v) = 1, then based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge -\frac{1}{2}+2\times \frac{2}{7}+\mathrm{m}\mathrm{i}\mathrm{n}\{\frac{1}{8}+\frac{3}{8},2\times \frac{1}{4}\}=\frac{4}{7}>0. If n₃(v) = 0, then based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge -\frac{1}{2}+2\times \frac{2}{7}+2\times \frac{1}{8}+\frac{1}{4}=\frac{4}{7}>0.

When vertex v is not associated with a 3-face, we have n₃(v) \le 2. If n₃(v) = 2, then based on (R3), {\omega }^{\prime }\left(v\right)\ge -\frac{1}{2}+\frac{1}{2}=0. If n₃(v) = 1, then based on (R2), {\omega }^{\prime }\left(v\right)\ge -\frac{1}{2}+\mathrm{m}\mathrm{i}\mathrm{n}\{\frac{1}{8}+\frac{3}{8},2\times \frac{1}{4}\}=0. If n₃(v) = 0, then based on (R2), {\omega }^{\prime }\left(v\right)\ge -\frac{1}{2}+2\times \frac{1}{8}+\frac{1}{4}=0.

(3) d(v) = 4, ω(v) = 1. According to Lemma 3.5, n₂(v) \le d(v) − 2 = 2.

When n₂(v) = 2, according to Lemma 3.8 and Lemma 3.9, m₃(v) = 0 and n₃(v) = 0. According to (P3) and (P4), m_{7^{+}}(v) \ge 1. Based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge 1+\frac{2}{7}-2\times \frac{9}{14}=0.

When n₂(v) = 1, if vertex v is associated with a 3-face, then according to Lemma 3.6 and Lemma 3.10, δ(f) \ge 4. According to (P1), m_{7^{+}}(v) \ge 2. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge 1+2\times \frac{2}{7}-\frac{9}{14}-\frac{1}{8}-\frac{2}{3}=\frac{23}{168}>0. If vertex v is not associated with a 3-face, then n₃(v) \le 3. According to (P3) and (P4), m_{7^{+}}(v) \ge 1. Based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge 1+\frac{2}{7}-\frac{9}{14}-3\times \frac{1}{8}=\frac{15}{56}>0.

When n₂(v) = 0, if vertex v is associated with a 3-face, then according to Lemma 3.7, n₃(v) \le 3. According to (P1) and (P3), m_{7^{+}}(v) \ge 2. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge 1+2\times \frac{2}{7}-\frac{9}{14}-\frac{1}{8}-\frac{2}{3}=\frac{23}{168}>0. If vertex v is not associated with a 3-face, then n₃(v) \le 4. According to (R2), {\omega }^{\prime }\left(v\right)\ge 1-4\times \frac{1}{8}=\frac{1}{2}>0.

(4) d(v) = 5, ω(v) = \frac{5}{2}. According to Lemma 3.5, n₂(v) \le d(v) − 2 = 3.

When n₂(v) = 3, if vertex v is associated with a 3-face f, then according to Lemma 3.11 and Lemma 3.12, δ(f) \ge 4. According to (P1) and (P4), m_{7^{+}}(v) \ge 3. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+3\times \frac{2}{7}-3\times \frac{11}{14}-\frac{2}{3}=\frac{1}{3}>0. If vertex v is not associated with a 3-face, then n₃(v) \le 2. According to (P4), m_{7^{+}}(v) \ge 2. Based on (R1) to (R3), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+2\times \frac{2}{7}-3\times \frac{11}{14}-2\times \frac{1}{4}=\frac{3}{14}>0.

When n₂(v) = 2, if vertex v is associated with a 3-face, then if the 2-point is associated with a 3-face, according to Lemma 3.6, n₃(v) \le 2. According to (P1) and (P2), m_{7^{+}}(v) \ge 2, and at least one of them is an 8⁺-face. Based on (R1) to (R4), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+\frac{2}{7}+\frac{3}{8}-2\times \frac{11}{14}-2\times \frac{1}{4}-1=\frac{5}{56}>0. If the 2-point is not associated with a 3-face, then according to Lemma 3.7, n₃(v) \le 2. According to (P1) and (P4), m_{7^{+}}(v) \ge 2. Based on (R1) to (R4), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+2\times \frac{2}{7}-2\times \frac{11}{14}-\mathrm{m}\mathrm{a}\mathrm{x}\{2\times \frac{1}{4}+1,\frac{1}{4}+\frac{2}{3}\}=0. If vertex v is not associated with a 3-face, then n₃(v) \le 3. According to (P3) and (P4), m_{7^{+}}(v) \ge 1. Based on (R1) to (R3), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+\frac{2}{7}-2\times \frac{11}{14}-3\times \frac{1}{4}=\frac{13}{28}>0.

When n₂(v) = 1, if vertex v is associated with a 3-face, then if the 2-point is associated with a 3-face, according to Lemma 3.6, n₃(v) \le 3. According to (P1) and (P2), m_{7^{+}}(v) \ge 2, and at least one of them is an 8⁺-face. Based on (R1) to (R4), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+\frac{2}{7}+\frac{3}{8}-\frac{11}{14}-3\times \frac{1}{4}-1=\frac{5}{8}>0. If the 2-point is not associated with a 3-face, then according to Lemma 3.7, n₃(v) \le 3. According to (P1) and (P4), m_{7^{+}}(v) \ge 2. Based on (R1) to (R4), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+2\times \frac{2}{7}-\frac{11}{14}-\mathrm{m}\mathrm{a}\mathrm{x}\{3\times \frac{1}{4}+1,2\times \frac{1}{4}+\frac{2}{3}\}=\frac{15}{28}>0. If vertex v is not associated with a 3-face, then n₃(v) \le 4. According to (P3) and (P4), m_{7^{+}}(v) \ge 1. Based on (R1) to (R3), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+\frac{2}{7}-\frac{11}{14}-4\times \frac{1}{4}=1>0.

When n₂(v) = 0, if vertex v is associated with a 3-face, then according to Lemma 3.7, n₃(v) \le 4. According to (P1), m_{7^{+}}(v) \ge 2. Based on (R1), (R3), and (R4), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}+2\times \frac{2}{7}-\mathrm{m}\mathrm{a}\mathrm{x}\{4\times \frac{1}{4}+1,3\times \frac{1}{4}+\frac{2}{3}\}=\frac{15}{14}>0. If vertex v is not associated with a 3-face f, then n₃(v) \le 5. According to (R3), {\omega }^{\prime }\left(v\right)\ge \frac{5}{2}-5\times \frac{1}{4}=\frac{5}{4}>0.

(5) d(v) = 6, ω(v) = 4. According to Lemma 3.5, n₂(v) \le d(v) − 2 = 4.

(5.1) Vertex v is associated with a 3-face f. According to Lemma 3.7, n₃(v) \le d(v) − 1 − n₂(v) = 5 − n₂(v).

(5.1.1) n₂(v) = 0.

According to (P1), m_{7^{+}}(v) \ge 2. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge 4+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{3}{8}{n}_3\left(v\right)-m_3\left(v\right)\ge \begin{array}{r}4+2\times \frac{2}{7}-5\times \frac{3}{8}-1=\frac{95}{56}>0.\end{array}

(5.1.2) n₂(v) ≠ 0.

(a) f is associated with a 2-point.

When 1 \le n₂(v) \le 3, according to (P5), m_{7^{+}}(v) \ge 2, and at least one of them is an 8⁺-face. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge 4+\frac{2}{7}(m_{7^{+}}(v)-1)+\frac{3}{8}-\frac{195}{224}{n}_2\left(v\right)-\frac{3}{8}{n}_3\left(v\right)-1\ge 4+\frac{2}{7}+\frac{3}{8}-3\times \frac{195}{224}-2\times \frac{3}{8}-1=\frac{67}{224}>0.

When n₂(v) = 4, according to (P5), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+2}{2}=3, and at least one of them is an 8+-face. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge 4+\frac{2}{7}\left(m_{7^{+}}\left(v\right)-1\right) + \frac{3}{8}-\frac{195}{224}{n}_2\left(v\right)-\frac{3}{8}{n}_3\left(v\right)-1\ge 4+2\times \frac{2}{7}+\frac{3}{8}-4\times \frac{195}{224}-\frac{3}{8}-1=\frac{5}{56}>0.

(b) f is not associated with a 2-point.

According to (P6), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+2}{2}. Based on (R1), (R2), and (R4), {\omega }^{\prime }\left(v\right)\ge 4+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{195}{224}{n}_2\left(v\right)-\frac{3}{8}{n}_3\left(v\right)-m_3\left(v\right)\ge 4+\frac{2}{7}\times \frac{n_2\left(v\right)+2}{2}-\frac{195}{224}{n}_2\left(v\right) − \frac{3}{8}\times (5-n_2\left(v\right))-1=\frac{79}{56}-\frac{79}{224}{n}_2\left(v\right)\ge \frac{79}{56}-4\times \frac{79}{224}=0.

(5.2) Vertex v is not associated with any 3-face, and we have n_3\left(v\right)\le d\left(v\right)-n_2\left(v\right)=6-n_2\left(v\right).

(5.2.1) n₂(v) = 0. According to (R2), {\omega }^{\prime }\left(v\right)\ge 4-6\times \frac{3}{8}=\frac{7}{4}>0.

(5.2.2) n₂(v) ≠ 0.

According to (P7), m_{7^{+}}\left(\mathrm{v}\right)\ge \frac{n_2\left(v\right)}{2}. Based on (R1) and (R2), {\omega }^{\prime }\left(v\right)\ge 4+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{195}{224}{n}_2\left(v\right)-\frac{3}{8}{n}_3\left(v\right)\ge 4+\frac{2}{7}\times \frac{n_2\left(v\right)}{2}-\frac{195}{224}{n}_2\left(v\right)-\frac{3}{8}\times \left(6-n_2\left(v\right)\right) = \frac{7}{4}-\frac{79}{224}{n}_2\left(v\right)\ge \frac{7}{4}-4\times \frac{79}{224}=\frac{19}{56}>0.

(6) d(v) = 7, ω(v) = \frac{11}{2}. According to Lemma 3.5, we have n₂(v) \le d(v) − 2 = 5.

(6.1) Vertex v is associated with a 3-face f. According to Lemma 3.7 and (P1), we have n₃(v) \le d(v) − 1 − n₂(v) = 6 − n₂(v), and m_{7^{+}}(v) \ge 2.

(6.1.1) n₂(v) = 0.

Based on (R1)−(R4), {\omega }^{\prime }\left(v\right)\ge \frac{11}{2}+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-m_3\left(v\right)\ge \frac{11}{2}+2\times \frac{2}{7}-6\times \frac{1}{2}-1=\frac{29}{14}>0.

(6.1.2) n₂(v) ≠ 0.

(a) f is associated with a 2-point.

When 1 \le n₂(v) \le 3, according to (P5), m_{7^{+}}(v) \ge 2, and at least one of them is an 8⁺-face. Based on (R1)‒(R4), {\omega }^{\prime }\left(v\right)\ge \frac{11}{2}+\frac{2}{7}\left(m_{7^{+}}\left(v\right)-1\right)+\frac{3}{8}-\frac{277}{280}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-1\ge \frac{11}{2}+\frac{2}{7}+\frac{3}{8}-3\times \frac{277}{280}-3\times \frac{1}{2}-1=\frac{97}{140}>0.

When 4 \le n₂(v) \le 5, according to (P5), taking m_{7^{+}}\left(\mathrm{v}\right)\ge \frac{n_2\left(v\right)+1}{2}, and at least one of them is an 8+-face. Based on (R1)−(R4), {\omega }^{\prime }\left(v\right)\ge \frac{11}{2}+\frac{2}{7}(m_{7^{+}}(v)-1)+\frac{3}{8}-\frac{277}{280}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-1\ge \frac{11}{2}+\frac{2}{7}\times \frac{n_2\left(v\right)-1}{2}+\frac{3}{8}-\frac{277}{280}{n}_2\left(v\right)-\frac{1}{2}\times \left(6-n_2\left(v\right)\right) − 1 = \frac{97}{56}-\frac{97}{280}{n}_2\left(v\right)\ge \frac{97}{56}-5\times \frac{97}{280}=0.

(b) f is not associated with a 2-point.

According to (P6), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+2}{2}. Based on (R1)−(R4), {\omega }^{\prime }\left(v\right)\ge \frac{11}{2}+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{27}{280}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-m_3\left(v\right)\ge \frac{11}{2}+\frac{2}{7}\times \frac{n_2\left(v\right)+2}{2}-\frac{277}{280}{n}_2\left(v\right)-\frac{1}{2} × (6-n_2\left(v\right))-1=\frac{25}{14}-\frac{97}{280}{n}_2\left(v\right)\ge \frac{25}{14}-5\times \frac{97}{280}=\frac{3}{56}>0.

(6.2) Vertex v is not associated with any 3-face, and we have n₃(v) ⩽ d(v) − n₂(v) = 6 − n₂(v).

(6.2.1) n₂(v) = 0. According to (R3), {\omega }^{\prime }\left(v\right)\ge \frac{11}{2}-7\times \frac{1}{2}=2>0.

(6.2.2) n₂(v) ≠ 0.

According to (P7), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)}{2}. Based on (R1)−(R3), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)}{2}.

(7) d(v) = d \ge 8, ω(v)=\frac{3}{2}d−5. According to Lemma 3.5, we have n₂(v) \le d − 2.

(7.1) Vertex v is associated with a 3-face f. According to Lemma 3.7, we have n₃(v) \le d − 1 − n₂(v).

(7.1.1) n₂(v) = 0.

Based on (P5), m_{7^{+}}(v) \ge 2. According to (R1), (R3), and (R4), {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-m_3\left(v\right)\ge \frac{3}{2}d-5+2\times \frac{2}{7}-\frac{1}{2}\times \left(d-1\right)-1 = d-\frac{69}{14}>0.

(7.1.2) n₂(v) ≠ 0.

(a) f is associated with a 2-point.

When 1 \le n₂(v) \le 3, according to (P₅), m_{7^{+}}(v) \ge 2, and v is associated with at least one 8⁺-face. Based on (R1)‒(R4), {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5+\frac{2}{7}(m_{7^{+}}\left(v\right)-1)+\frac{3}{8}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-1\ge \frac{3}{2}d-5+\frac{2}{7}+\frac{3}{8}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}\times \left(d-1-n_2\left(v\right)\right)-1 = d-\frac{17}{28}{n}_2\left(v\right)-\frac{271}{56}\ge d-3\times \frac{17}{28}-\frac{271}{56}=d-\frac{373}{56}>0.

When 4⩽n_2(v)⩽d-2, if n₂(v) is odd, then according to (R1)‒(R4), for d = 8, {\omega }^{\prime }\left(v\right)\ge 7+2\times \frac{2}{7}+\frac{3}{8}-5\times \frac{93}{84}-2\times \frac{1}{2}-1=\frac{161}{392}>0; for d⩾9, {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5 + \frac{2}{7}\left(m_{7^{+}}\left(v\right)-1\right)+\frac{3}{8}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-1\ge \frac{3}{2}d-5+\frac{2}{7}\times \frac{n_2\left(v\right)-1}{2} + \frac{3}{8}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}\times \left(d-1-n_2\left(v\right)\right)-1=d-\frac{13}{28}{n}_2\left(v\right)-\frac{295}{56}\ge d-\frac{13}{28}\times \left(d-2\right)-\frac{295}{56} = \frac{15}{28}d-\frac{243}{56}>0. If n₂(v) is even, then according to (R1)−(R4), {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5+\frac{2}{7}(m_{7^{+}}\left(v\right)-1)+\frac{3}{8}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-1\ge \frac{3}{2}d-5 + \frac{2}{7}\times \frac{n_2\left(v\right)}{2}+\frac{3}{8}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}\times (d-1-n_2\left(v\right))-1 = d-\frac{13}{28}{n}_2\left(v\right)-\frac{41}{8}\ge d-\frac{13}{28}\times \left(d-2\right)-\frac{41}{8}=\frac{15}{28}d-\frac{235}{56}>0.

(b) f is not associated with a 2-point.

According to (P6), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)+2}{2}. Based on (R1)−(R4), {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)-1\ge \frac{3}{2}d-5+\frac{2}{7}\times \frac{n_2\left(v\right)+2}{2}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2} × (d-1-n_2\left(v\right))-1 = d-\frac{13}{28}{n}_2\left(v\right)-\frac{73}{14}\ge d-\frac{13}{28}\times \left(d-2\right)-\frac{73}{14}=\frac{15}{28}d-\frac{30}{7}\ge 0.

(7.2) Vertex v is not associated with any 3-face, and we have n₃(v) \le d − n₂(v).

(7.2.1) n₂(v)= 0.

According to (R3), {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5-\frac{1}{2}{n}_3\left(v\right)\ge \frac{3}{2}d-5-\frac{1}{2}d=d-5>0.

(7.2.2) n₂(v) ≠ 0.

Based on (P7), m_{7^{+}}\left(v\right)\ge \frac{n_2\left(v\right)}{2}. According to (R1)−(R3), {\omega }^{\prime }\left(v\right)\ge \frac{3}{2}d-5+\frac{2}{7}{m}_{7^{+}}\left(v\right)-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}{n}_3\left(v\right)\ge \frac{3}{2}d-5+\frac{2}{7}\times \frac{n_2\left(v\right)}{2}-\frac{93}{84}{n}_2\left(v\right)-\frac{1}{2}\times \left(d-n_2\left(v\right)\right) = d-\frac{13}{28}{n}_2\left(v\right)-5\ge d-\frac{13}{28}\times \left(d-2\right)-5=\frac{15}{28}d-\frac{57}{14}>0.

By applying the weight transformation rules (R1)−(R4), we have shown that for all vertices v \in V(G), {\omega }^{\mathrm{\prime }}(v) \ge 0. Similarly, for each face f \in F(G), when d(f) = 3, according to (R4), {\omega }^{\prime }\left(f\right)\ge -2+\mathrm{m}\mathrm{i}\mathrm{n}\{2\times 1,3\times \frac{2}{3}\}=0; when d(f) = 5, {\omega }^{\prime }\left(f\right)=\omega \left(f\right)=d\left(f\right)-5=0; when d(f) \ge 7, according to (R4), {\omega }^{\prime }\left(f\right)=d\left(f\right)-5-\frac{d\left(f\right)-5}{d\left(f\right)}\times d\left(f\right)=0.

Therefore, we have

{\sum }_{x\in V\left(G\right)\cup F\left(G\right)}\omega \left(x\right)={\sum }_{x\in V\left(G\right)\cup F\left(G\right)}\omega {}^{\prime }\left(x\right)\ge 0.

This contradicts the fact that \sum _{x\in V\left(G\right)\cup F\left(G\right)} \omega \left(x\right)=-10, which implies that G does not exist. Thus, Theorem 1.1 is proven to be true.

References

[1] Alon N, McDiarmid C, Reed B. Acyclic coloring of graphs. Random Structures Algorithms 1991; 2(3): 277–288

[2] Basavaraju M, Chandran L S, Cohen N, Havet F, Mülle T. Acyclic edge-coloring of planar graphs. SIAM J Discrete Math 2011; 25(2): 463–478

[3] Fialho P M S, de Lima B N B, Procacci A. A new bound on the acyclic edge chromatic number. Discrete Math 2020; 343(11): 112037

[4] Fiamčík J. The acyclic chromatic class of a graph. Math. Slovaca 1978; 28(2): 139–145

[5] Hou J F, Liu G Z, Wu J L. Acyclic edge coloring of planar graphs without small cycles. Graphs Combin 2012; 28(2): 215–226

[6] Hou J F, Wang W T, Zhang X R. Acyclic edge coloring of planar graphs with girth at least 5. Discrete Appl Math 2013; 161(18): 2958–2967

[7] Hudák D, Kardoš F, Lužar B, Soták R, Škrekovski R. Acyclic edge coloring of planar graphs with ∆ colors. Discrete Appl Math 2012; 160(9): 1356–1368

[8] KirousisLLivieratosJ. The acyclic chromatic index is less than the double of the max degree. 2022, arXiv: 1901.07856v7

[9] MolloyMReedB. Further algorithmic aspects of the local lemma, In: STOC ’98 (Dallas, TX). New York: ACM, 1999, 524−529

[10] Shu Q J, Chen Y, Han S G, Lin G H, Miyano E, Zhang A. Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles. Theoret Comput Sci 2021; 882: 77–108

[11] Shu Q J, Wang W F, Wang Y Q. Acyclic edge coloring of planar graphs without 5-cycles. Discrete Appl Math 2012; 160(7/8): 1211–1223

[12] Shu Q J, Wang W F, Wang Y Q. Acyclic chromatic indices of planar graphs with girth at least 4. J Graph Theory 2013; 73(4): 386–399

[13] Wang T, Zhang Y Q. Further result on acyclic chromatic index of planar graphs. Discrete Appl Math 2016; 201: 228–247

[14] Wang W F, Shu Q J, Wang K, Wang P. Acyclic chromatic indices of planar graphs with large girth. Discrete Appl Math 2011; 159(12): 1239–1253

[15] Wang W F, Shu Q J, Wang Y Q. A new upper bound on the acyclic chromatic indices of planar graphs. European J Combin 2013; 34(2): 338–354

[16] Wang W F, Shu Q J, Wang Y Q. Acyclic edge coloring of planar graphs without 4-cycles. J Comb Optim 2013; 25(4): 562–586

[17] Wang Y Q, Shu Q J. Acyclic edge coloring of planar graphs. J Jiangsu Norm Univ (Nat Sci Ed) 2014; 32(3): 22–26

[18] Wang Y Q, Shu Q J, Wang W F. The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle. Discrete Appl Math 2013; 161(16/17): 2687–2694

[19] Wang Y Q, Shu Q J, Wu J L, Zhang W W. Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle. J Comb Optim 2014; 28(3): 692–715

[20] Wang Y Q, Sheng P. Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles. J Comb Optim 2014; 27(3): 519–529

[21] Xie D Z, Wu Y Q. Acyclic edge coloring of planar graphs without adjacent triangles. J Math Res Appl 2012; 32(4): 407–414

RIGHTS & PERMISSIONS

Higher Education Press 2024