On the (Δ + 2)-Total-Colorability of Planar Graphs with 7-Cycles Containing at Most Two Chords

Jian Chang^1,2*, Jingru Liu¹, Fan Zhang¹

¹College of Mathematics Science, Inner Mongolia Normal University, Hohhot, China.
²Laboratory of Infinite-Dimensional Hamiltonian System and Its Algorithm Application, Hohhot, China.

DOI: 10.4236/jamp.2024.127161                

Abstract

The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.

Keywords

Planar Graph, 7-Cycle, 8-Totally-Colorable, Maximum Degree

1. Introduction

In this paper, we consider only finite, simple, undirected graphs, and follow [1] for the undefined terminology and notation here. Given a graph G, we denote its vertex set, edge set and maximum degree by $V\left(G\right)$ , $E\left(G\right)$ and $\Delta \left(G\right)$ (or simply V, E and Δ), respectively. A cycle of length $k$ is called a $k$ -cycle, two cycles C₁ and C₂ are said to intersecting (resp., adjacent) if C₁ and C₂ share at least one vertex (resp., one edge). A 3-cycle is also called a triangle. For a cycle C of G, an edge $xy\in E\left(G\right)\backslash E\left(C\right)$ is called a chord of C if $x\mathrm{,}y\in V\left(C\right)$ .

A $k$ -total-coloring of graph G is a coloring of $V\cup E$ using $k$ colors such that no two adjacent or incident elements receive the same color. A graph G is $k$ -totally-colorable if it admits a $k$ -total-coloring. Obviously, at least Δ + 1 colors are necessitated to color G totally. Behzad [2] and Vizing [3] independently put forward the following conjecture, which is well known as the Total Coloring Conjecture (TCC).

Conjecture Every graph is (Δ + 2)-totally-colorable.

Clearly, TCC is true for Δ ≤ 2. Rosenfeld [4] and Vijayaditya [5] solved it for Δ = 3. Kostochka solved the cases of Δ = 4 [6] and Δ = 5 [7] successively. For planar graphs, more results are known, TCC is true for Δ = 7 [8], and Δ ≥ 8 [9]. So the only open case for planar graphs is Δ = 6. While TCC remains unsolved for general planar graphs G with Δ = 6, it is known to hold for some special cases, as follows.

Theorem 1. Let G be a planar graph with Δ = 6. Then G is 8-totally-colorable if one of the following conditions holds.

(1) G contains no adjacent triangles (see [10]).

(2) G contains no chordal $k$ -cycles for some $k\in \left\{\mathrm{4,5,6}\right\}$ (see [11]).

(3) For every vertex $x$ of G, there is an integer $k_x\in \left\{\mathrm{3,4,5,6,7,8}\right\}$ , such that $x$ is not in any $k_x$ -cycle (see [12]).

(4) $v_5^4+2\left(v_5^{5^{+}}+v_6^4\right)+3v_6^5+4v_6^{6^{+}}<24$ , where $v_n^k$ denotes the number of vertices of degree $n$ that lie on $k$ distinct triangles in G (see [13]).

(5) G contains no any subgraph isomorphic to a 4-fan (see [14]).

(6) G is claw-free (see [15]).

(7) G is recursive maximal (see [16]).

In this paper, we obtain the following result.

Theorem 2. Let G be a planar graph with Δ = 6. If every 7-cycle of G contains at most two chords, then G is 8-totally-colorable.

On the other hand, Shen et al. [17] conjectured that every planar graph is (Δ + 1)-totally-colorable, for $4\le \Delta \le 8$ . This first result was given in [18] for Δ ≥ 14, which was finally improved to Δ ≥ 9 in [19]. Some related results can be found in [20]-[30].

Now, we define some more definitions and notations. A vertex of degree $k$ , at most $k$ or at least $k$ is called a $k$ -vertex, $k^{-}$ -vertex or a $k^{+}$ -vertex, respectively. A $k$ -face (resp., $k^{-}$ -face, $k^{+}$ -face) is a face of degree $k$ (resp., at most $k$ , at least $k$ ). A face $f=\left(v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_k\right)$ with consecutive vertices $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_k$ along its boundary is called a $\left(d\left(v_1\right)\mathrm{,}d\left(v_2\right)\mathrm{,}\cdots \mathrm{,}d\left(v_k\right)\right)$ -face. Denote by $f_k\left(v\right)$ the number of $k$ -faces incident with $v$ , by $f_b\left(v\right)$ the number of $\left(\mathrm{4,5,6}\right)$ -faces incident with $v$ .

2. Proof of Theorem 2

Let $G=\left(V\mathrm{,}E\mathrm{,}F\right)$ be a minimal counterexample to Theorem 2, such that $\left|V\right|+\left|E\right|$ is minimum. Thus every proper subgraph of G admits an 8-total-coloring. Embed G into the plane, and denoted face set of G by F. We first show some structure properties of G.

Lemma 3. ([10]) (1) G is 2-connected.

(2) G contains no edge $uv$ with $\min \left\{d\left(u\right)\mathrm{,}d\left(v\right)\right\}\le 3$ and $d\left(u\right)+d\left(v\right)\le 8$ .

By Lemma 3(1), if $f$ is a face of G, then the boundary of $f$ is a cycle. By Lemma 3(2), $\delta \ge 3$ and if $v$ is 3-vertex of G, then the three neighbors of $v$ are all 6-vertices.

Lemma 4. ([13]) (1) G contains no $\left(\mathrm{3,6,6}\right)$ -triangle.

(2) G contains no $\left(\mathrm{4,4,6}\right)$ -triangle.

(3) G contains no $\left({\mathrm{4,5}}^{-}{\mathrm{,5}}^{-}\right)$ -triangle.

Lemma 5. ([13] [14]) If $\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ is a triangle in G, where $d\left(v_1\right)=4$ , $d\left(v_2\right)=5$ and $d\left(v_3\right)=6$ , then

(1) both $v_1{v}_2$ and $v_1{v}_3$ are only incident with one triangle, i.e. $\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ .

(2) $v_2{v}_3$ is only incident with one $\left(\mathrm{4,5,6}\right)$ -triangle, i.e. $\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ .

(3) $v_3$ is not adjacent to any 3-vertex.

Lemma 6. ([13]) (1) G contains no 4-face incident with more than one 3-vertex.

(2) G contains no 5-face incident with more than one 3-vertex.

We shall complete the proof of Theorem 2 by using the discharging method. According to the Euler’s formula $\left|V\right|-\left|E\right|+\left|F\right|=2$ , we have

${\displaystyle \sum _{v\in V}}\left(2d\left(v\right)-6\right)+{\displaystyle \sum _{f\in F}}\left(d\left(f\right)-6\right)=-12<0.$

For each $x\in V\cup F$ , we define $ch\left(x\right)$ to be the initial charge of $x$ . In particular, $ch\left(x\right)=2d\left(x\right)-6$ ($x\in V$ ), $ch\left(x\right)=2d\left(x\right)-6$ ($x\in F$ ). Obviously, ${\displaystyle {\sum }_{x\in V\cup F}}ch\left(x\right)=-12$ . Then, we will apply the following discharging rules to reassign a new charge denoted by $c{h}^{\prime }\left(x\right)$ . If we can get $c{h}^{\prime }\left(x\right)\ge 0$ , then we obtain an obvious contradiction to $0\le {\displaystyle {\sum }_{x\in V\cup F}}c{h}^{\prime }\left(x\right)=-12$ , and complete the proof.

For a face $f=\left(v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_k\right)$ of G, we use

$\left(d\left(v_1\right)\mathrm{,}d\left(v_2\right)\mathrm{,}\cdots \mathrm{,}d\left(v_k\right)\right)\to \left(c_1\mathrm{,}{c}_2\mathrm{,}\cdots \mathrm{,}{c}_k\right)$

to denote that $v_i$ sends $c_i$ to $f$ for $i=\mathrm{1,2,}\cdots \mathrm{,}k$ . Define the discharging rules that we need as follows.

R1. For $f=\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\mathrm{,}{v}_5\right)$ , we have

$\left({\mathrm{3,6,4}}^{+}{\mathrm{,4}}^{+}\mathrm{,6}\right)\to \left(\mathrm{0,}\frac{1}{4}\mathrm{,}\frac{1}{4}\mathrm{,}\frac{1}{4}\mathrm{,}\frac{1}{4}\right)$ ,

$\left(4^{+}{\mathrm{,4}}^{+}{\mathrm{,4}}^{+}{\mathrm{,4}}^{+}{\mathrm{,4}}^{+}\right)\to \left(\frac{1}{5}\mathrm{,}\frac{1}{5}\mathrm{,}\frac{1}{5}\mathrm{,}\frac{1}{5}\mathrm{,}\frac{1}{5}\right)$ .

R2. For $f=\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right)$ , we have

$\left({\mathrm{3,6,4}}^{+}\mathrm{,6}\right)\to \left(\mathrm{0,}\frac{3}{4}\mathrm{,}\frac{1}{2}\mathrm{,}\frac{3}{4}\right)$ ,

$\left(4^{+}{\mathrm{,4}}^{+}{\mathrm{,4}}^{+}{\mathrm{,4}}^{+}\right)\to \left(\frac{1}{2}\mathrm{,}\frac{1}{2}\mathrm{,}\frac{1}{2}\mathrm{,}\frac{1}{2}\right)$ .

R3. For any 5-vertex $v$ and $f=\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ , let $\eta \left(v\right)=\left(ch\left(v\right)-\frac{1}{2}{f}_4\left(v\right)-\frac{1}{4}{f}_5\left(v\right)\right)/f_3\left(v\right)$ . In addition,

$\left(\mathrm{4,5,6}\right)\to \left(\frac{1}{2}\mathrm{,}\eta \left(v_2\right)\mathrm{,}\frac{5}{2}-\eta \left(v_2\right)\right)$ ,

$\left(\mathrm{4,6,6}\right)\to \left(\frac{1}{2}\mathrm{,}\frac{5}{4}\mathrm{,}\frac{5}{4}\right)$ ,

$\left(\mathrm{5,5,5}\right)\to \left(\eta \left(v_1\right)\mathrm{,}\eta \left(v_2\right)\mathrm{,}\eta \left(v_3\right)\right)$ ,

$\left(\mathrm{5,5,6}\right)\to \left(\eta \left(v_1\right)\mathrm{,}\eta \left(v_2\right)\mathrm{,3}-\eta \left(v_1\right)-\eta \left(v_2\right)\right)$ ,

$\left(\mathrm{5,6,6}\right)\to \left(\eta \left(v_1\right)\mathrm{,}\frac{3-\eta \left(v_1\right)}{2}\mathrm{,}\frac{3-\eta \left(v_1\right)}{2}\right)$ ,

$\left(\mathrm{6,6,6}\right)\to \left(\mathrm{1,1,1}\right)$ .

For every vertex $v$ and every face $f$ , we will check that $c{h}^{\prime }\left(v\right)\ge 0$ and $c{h}^{\prime }\left(f\right)\ge 0$ . Denote by $c\left(v\to f\right)$ the total charge from $v$ to $f$ .

Let $f\in F$ . If $f$ is a 6⁺-face, then $c{h}^{\prime }\left(f\right)=ch\left(f\right)=d\left(f\right)-6\ge 0$ . If $f$ is a 5-face, then $c{h}^{\prime }\left(f\right)\ge -1+\min \left\{4\times \frac{1}{4}\mathrm{,5}\times \frac{1}{5}\right\}=0$ by Lemma 3, Lemma 6(2) and R1. If $f$ is a 4-face, then $c{h}^{\prime }\left(f\right)\ge -2+\min \left\{2\times \frac{3}{4}+\frac{1}{2}\mathrm{,4}\times \frac{1}{2}\right\}=0$ by Lemma 3, Lemma 6(1) and R2.

Suppose $f=\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ is a 3-face. If $\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ is not a $\left(\mathrm{5,5,5}\right)$ -face, then $c{h}^{\prime }\left(f\right)\ge -3+3=0$ by Lemma 3, Lemma 4 and R3. Now we consider the case that $\left(v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right)$ is a $\left(\mathrm{5,5,5}\right)$ -face, that is, $v_1$ , $v_2$ and $v_3$ are all 5-vertices. By

R3, $v_i$ transfers at least $\frac{4}{5}$ to each 3-face incident with $v_i$ $\left(i=\mathrm{1,2,3}\right)$ . By R1 and R2, $v_i$ transfers at most $\frac{1}{2}$ to each 4⁺-face incident with $v_i$ $\left(i=\mathrm{1,2,3}\right)$ . Thus if $f_3\left(v_i\right)\le 3$ , then $c\left(v_i\to f\right)\ge \left(4-2\times \frac{1}{2}\right)/3=1$ $\left(i=\mathrm{1,2,3}\right)$ , we have

$c{h}^{\prime }\left(f\right)\ge -3+3\times 1=0$ . Otherwise, without loss of generality (WLOG), assume $f_3\left(v_1\right)\ge 4$ , it follows that both $v_2$ and $v_3$ must be incident with at least two 5⁺-faces, i.e. $f_{5^{+}}\left(v_2\right)\ge 2$ and $f_{5^{+}}\left(v_3\right)\ge 2$ . Therefore,

$c\left(v_i\to f\right)\ge 4-2\times \frac{1}{4}/3=\frac{7}{6}$ $\left(i=\mathrm{2,3}\right)$ ,

we have $c{h}^{\prime }\left(f\right)\ge -3+\frac{4}{5}+\frac{7}{6}+\frac{7}{6}=\frac{2}{15}>0$ .

Let $v\in V$ . If $v$ is a 3-vertex, then $c{h}^{\prime }\left(v\right)=ch\left(v\right)=2d\left(v\right)-6=0$ . If $v$ is a 4-vertex or 5-vertex, then $c{h}^{\prime }\left(v\right)\ge 0$ according to the above discharging rules.

Suppose $v$ is a 6-vertex. Let $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_6$ be all the neighbors of $v$ and $f_1\mathrm{,}{f}_2\mathrm{,}\cdots \mathrm{,}{f}_6$ be all the faces incident with $v$ , where $f_m$ is incident with $v_m$ , $v_{m+1}$ , and $m\in \left\{\mathrm{1,2,}\cdots \mathrm{,6}\right\}$ . In general, each subscript of this paper is taken modulo 6. First, we give two lemmas.

Lemma 7. If $\left(v_i\mathrm{,}{v}_{i+1}\mathrm{,}v\right)$ and $\left(v_j\mathrm{,}{v}_{j+1}\mathrm{,}v\right)$ are two triangles in G, where $d\left(v_i\right)=4$ , $d\left(v_{i+1}\right)=5$ and $d\left(v\right)=6$ , then both $v_j$ and $v_{j+1}$ are 5⁺-vertices.

Proof. By Lemma 3 and Lemma 4, we have min$\left\{d\left(v_j\right)\mathrm{,}d\left(v_{j+1}\right)\right\}\ge 4$ and max$\left\{d\left(v_j\right)\mathrm{,}d\left(v_{j+1}\right)\right\}\ge 5$ . Assume to be contrary that $d\left(v_j\right)=4$ or $d\left(v_{j+1}\right)=4$ . WLOG, suppose that $d\left(v_j\right)=4$ . Let $N\left(v_i\right)=\left\{v_{i+1}\mathrm{,}v\mathrm{,}{u}_1\mathrm{,}{u}_2\right\}$ and $N\left(v_{i+1}\right)=\left\{v_i\mathrm{,}v\mathrm{,}{u}_3\mathrm{,}{u}_4\mathrm{,}{u}_5\right\}$ . We only need to consider the case that $v_j\ne v_i$ and $v_{j+1}\ne v_{i+1}$ by Lemma 5, see Figure 1(a).

The proof consists of two steps. First, we show that G has a partial 8-total-coloring in which only $v_i$ is not colored. Second, we show how to extend it to an 8-total-coloring of G. If $\phi$ is a (partial) 8-total-coloring of G, $v\in V$ , let $S\left(v\right)=\left\{\phi \left(vx\right)\mathrm{<mo>|</mo>}x\in N\left(v\right)\right\}$ , $S\left[v\right]=S\left(v\right)\cup \left\{\phi \left(e\right)\right\}$ . Consider a proper subgraph $G^{\prime }=G-v_i{v}_{i+1}$ of G, $G^{\prime }$ has a 8-total-coloring $\phi$ :

$V\left(G^{\prime }\right)\cup E\left(G^{\prime }\right)\to L=\left\{\mathrm{1,2,}\cdots \mathrm{,8}\right\}$ .

Erase the colors on $v_i$ . Clearly, $\left|S\left(v_i\right)\right|=3$ , $\left|S\left[v_{i+1}\right]\right|=5$ and $\left|S\left[v\right]\right|=7$ . Let $L\backslash S\left[v\right]=\left\{\alpha \right\}$ . If $S\left(v_i\right)\cap S\left[v_{i+1}\right]\ne \varnothing$ , then there are at most 7 forbidden colors for $v_i{v}_{i+1}$ , so $v_i{v}_{i+1}$ can be properly colored. Thus we can assume that $S\left(v_i\right)\cap S\left[v_{i+1}\right]=\varnothing$ (i.e. $S\left(v_i\right)\cup S\left[v_{i+1}\right]=L$ ), so $\alpha \in S\left(v_i\right)$ or $\alpha \in S\left[v_{i+1}\right]$ . If $\alpha \in S\left(v_i\right)$ , then we color $v_i{v}_{i+1}$ with $\phi \left(v{v}_{i+1}\right)$ , and recolor $v{v}_{i+1}$ with $\alpha$ . Otherwise, we color $v_i{v}_{i+1}$ with $\phi \left(v{v}_i\right)$ , and recolor $v{v}_i$ with $\alpha$ . Hence, G has such an 8-total-coloring.

Suppose now that $f$ is a partial 8-total-coloring of G in which only $v_i$ is uncolored. If we cannot extend $f$ to G, then there are exactly 8 forbidden colors for $v_i$ . WLOG, suppose that $f\left(u_1\right)=1$ , $f\left(u_2\right)=2$ , $f\left(v_{i+1}\right)=3$ , $f\left(v\right)=4$ , $f\left(v_i{u}_1\right)=5$ , $f\left(v_i{u}_2\right)=6$ , $f\left(v_i{v}_{i+1}\right)=7$ , $f\left(v{v}_i\right)=8$ , see Figure 1(b). Also let $L\backslash S\left[v\right]=\left\{\alpha \right\}$ . Obviously, $\left\{\mathrm{1,2,3,4}\right\}\subseteq \left(S\left[v_{i+1}\right]\cap S\left[v\right]\right)$ . Otherwise, we can choose a color $\beta \in \left\{\mathrm{1,2,3,4}\right\}\backslash S\left[v_{i+1}\right]$ or $\beta \in \left\{\mathrm{1,2,3,4}\right\}\backslash S\left[v\right]$ , recolor $v_i{v}_{i+1}$ or $v_{i}v$ with β, color $v_i$ with 7 or 8. Note that $f\left(v{v}_{i+1}\right)\in \left\{\mathrm{1,2,5,6}\right\}$ .

Figure 1. Configurations for the proof of Lemma 7, where vertices marked by • have no other neighbors.

Suppose $f\left(v{v}_{i+1}\right)\in \left\{\mathrm{1,2}\right\}$ . If $7\notin S\left[v\right]$ or $8\notin S\left[v_{i+1}\right]$ , then we exchange $f\left(v_i{v}_{i+1}\right)$ and $f\left(v{v}_{i+1}\right)$ , or $f\left(v{v}_i\right)$ and $f\left(v{v}_{i+1}\right)$ , color $v_i$ with 7 or 8. Otherwise, $S\left[v_{i+1}\right]=\left\{\mathrm{1,2,3,4,7,8}\right\}$ and $\left\{\mathrm{1,2,3,4,7,8}\right\}\subseteq S\left[v\right]$ , it follows that $S\left[v_{i+1}\right]\subseteq S\left[v\right]$ , we can recolor $v{v}_{i+1}$ with $\alpha$ , $v_i{v}_{i+1}$ with $f\left(v{v}_{i+1}\right)$ , color $v_i$ with 7. Suppose $f\left(v{v}_{i+1}\right)\in \left\{\mathrm{5,6}\right\}$ . WLOG, assume $f\left(v{v}_{i+1}\right)=5$ (i.e. $S\left[v_{i+1}\right]=\left\{\mathrm{1,2,3,4,5,7}\right\}$ and $\left\{\mathrm{1,2,3,4,5,8}\right\}\subseteq S\left[v\right]$ ). Then $\left\{\mathrm{6,8}\right\}\subseteq \left\{f\left(u_3\right)\mathrm{,}f\left(u_4\right)\mathrm{,}f\left(u_5\right)\right\}$ , for otherwise, we can recolor $v_{i+1}$ with 6 or 8, color $v_i$ with 3. Note that $\alpha \in \left\{\mathrm{6,7}\right\}$ .

If $\alpha =7$ (i.e. $S\left[v\right]=\left\{\mathrm{1,2,3,4,5,6,8}\right\}$ ), then $5\in \left\{f\left(u_3\right)\mathrm{,}f\left(u_4\right)\mathrm{,}f\left(u_5\right)\right\}$ . Otherwise, we can recolor $v{v}_{i+1}$ with 7, $v_{i+1}$ with 5, $v_i{v}_{i+1}$ with 3, and color $v_i$ with 7. Now we exchange $f\left(v{v}_i\right)$ and $f\left(v_i{v}_{i+1}\right)$ , recolor $v_{i+1}$ with 7, color $v_i$ with 3. In the rest of this proof we assume that $\alpha =6$ , then $S\left[v\right]=\left\{\mathrm{1,2,3,4,5,7,8}\right\}$ and $\left\{f\left(v{v}_j\right)\mathrm{,}f\left(v{v}_{j+1}\right)\right\}\cap \left\{\mathrm{5,6,8}\right\}=\varnothing$ , this situation is very complicated. First, we have $5\in \left\{f\left(u_3\right)\mathrm{,}f\left(u_4\right)\mathrm{,}f\left(u_5\right)\right\}$ , for otherwise, we can recolor $v{v}_{i+1}$ with 6, $v_{i+1}$ with 5, and color $v_i$ with 3. WLOG, suppose that $f\left(v_{i+1}{u}_3\right)=1$ , $f\left(v_{i+1}{u}_4\right)=2$ , $f\left(v_{i+1}{u}_5\right)=4$ , $f\left(u_3\right)=5$ , $f\left(u_4\right)=6$ ,$f\left(u_5\right)=8$ , see Figure 1(c). Second, we have $\left\{\mathrm{5,6,8}\right\}\subseteq S\left[v_j\right]$ , for otherwise, we can choose a color $\beta \in \left\{\mathrm{5,6,8}\right\}\backslash S\left[v_j\right]$ , recolor $v{v}_j$ with β, $v{v}_i$ with $f\left(v{v}_j\right)$ , color $v_i$ with 8 (here, we need to further recolor $v{v}_{i+1}$ with 6 when $\beta =5$ , and recolor $v_i{v}_{i+1}$ with 3 and $v_{i+1}$ with 7 when $f\left(v{v}_j\right)=7$ ). Similarly, $\left\{\mathrm{5,6,8}\right\}\subseteq S\left[v_{j+1}\right]$ . Let $f\left(v_j{v}_{j+1}\right)=\gamma$ . In terms of γ, there are the following two cases.

Case 1. $\gamma \in \left\{\mathrm{5,6,8}\right\}$ .

Then $f\left(v{v}_j\right)\in S\left[v_{j+1}\right]$ . Otherwise, we can exchange $f\left(v{v}_j\right)$ and $f\left(v_j{v}_{j+1}\right)$ , recolor $v{v}_i$ with $f\left(v{v}_j\right)$ , color $v_i$ with 8 (here, we need to further recolor $v{v}_{i+1}$ with 6 when $\gamma =5$ , and recolor $v_i{v}_{i+1}$ with 3 and $v_{i+1}$ with 7 when $f\left(v{v}_j\right)=7$ ). Similarly, $f\left(v{v}_{j+1}\right)\in S\left[v_j\right]$ . Thus $S\left[v_j\right]\subseteq S\left[v_{j+1}\right]$ , we can choose a color $\beta \in L\backslash S\left[v_{j+1}\right]$ , recolor $v_j{v}_{j+1}$ with β, $v{v}_j$ with γ, $v{v}_i$ with $f\left(v{v}_j\right)$ , color $v_i$ with 8 (here, we need to further recolor $v{v}_{i+1}$ with 6 when $\gamma =5$ , and recolor $v_i{v}_{i+1}$ with 3 and $v_{i+1}$ with 7 when $f\left(v{v}_j\right)=7$ ).

Case 2. $\gamma \notin \left\{\mathrm{5,6,8}\right\}$ .

Then $f\left(v_j\right)\in \left\{\mathrm{5,6,8}\right\}$ . If $\gamma \in \left\{f\left(u\right)\mathrm{<mo>|</mo>}u\in N\left(v_j\right)\right\}$ , then we choose $\beta \in \left\{\mathrm{1,2,3,4,7}\right\}\backslash \left\{f\left(u\right)\mathrm{<mo>|</mo>}u\in N\left(v_j\right)\right\}$ , recolor $v_j$ with β, $v{v}_j$ with $f\left(v_j\right)$ , $v{v}_i$ with $f\left(v{v}_j\right)$ , color $v_i$ with 8 (here, we need to further recolor $v{v}_{i+1}$ with 6 when $f\left(v_j\right)=5$ , and recolor $v_i{v}_{i+1}$ with 3 and $v_{i+1}$ with 7 when $f\left(v{v}_j\right)=7$ ). Otherwise, $\gamma \notin \left\{f\left(u\right)\mathrm{<mo>|</mo>}u\in N\left(v_j\right)\right\}$ . If $f\left(v{v}_j\right)\in S\left[v_{j+1}\right]$ , then $S\left[v_j\right]\subseteq S\left[v_{j+1}\right]$ , we choose a color $\beta \in L\backslash S\left[v_{j+1}\right]$ , recolor $v_j{v}_{j+1}$ with β, $v_j$ with γ, $v{v}_j$ with $f\left(v_j\right)$ , $v{v}_i$ with $f\left(v{v}_j\right)$ , color $v_i$ with 8 (here, we need to further recolor $v_i{v}_{i+1}$ with 3 and $v_{i+1}$ with 7 when $f\left(v{v}_j\right)=7$ ). Otherwise, $f\left(v{v}_j\right)\notin S\left[v_{j+1}\right]$ . Now we recolor $v_j{v}_{j+1}$ and $v{v}_i$ with $f\left(v{v}_j\right)$ , $v_j$ with γ, $v{v}_j$ with $f\left(v_j\right)$ , color $v_i$ with 8 (here, we need to further recolor $v{v}_{i+1}$ with 6 when $f\left(v_j\right)=5$ , and recolor $v_i{v}_{i+1}$ with 3 and $v_{i+1}$ with 7 when $f\left(v{v}_j\right)=7$ ).

All of the above show that G is 8-totally-colorable, a contradiction. $\square$

Lemma 8. Suppose $f_i=\left(v_i\mathrm{,}{v}_{i+1}\mathrm{,}v\right)$ is a triangle with $d\left(v\right)=6$ , we have

(1) If $d\left(v_i\right)=4$ and $d\left(v_{i+1}\right)=5$ , then $c\left(v\to f_i\right)\le \frac{13}{8}$ .

(2) If $d\left(v_i\right)=d\left(v_{i+1}\right)=5$ , then $c\left(v\to f_i\right)\le \frac{31}{30}$ .

Proof. (1) Note that $f_3\left(v_{i+1}\right)\le 4$ by Lemma 5(1), we have $c\left(v_{i+1}\to f_i\right)\ge \left(4-\frac{1}{2}\right)/4=\frac{7}{8}$ by R4, so $c\left(v\to f_i\right)\le \frac{5}{2}-\frac{7}{8}\mathrm{<mo>=</mo>}\frac{13}{8}$ .

(2) If $f_3\left(v_i\right)\le 3$ and $f_3\left(v_{i+1}\right)\le 3$ , then $c\left(v_i\to f_i\right)\ge \left(4-2\times \frac{1}{2}\right)/3=1$ and $c\left(v_{i+1}\to f_i\right)\ge \left(4-2\times \frac{1}{2}\right)/3=1$ , so $c\left(v\to f_i\right)\le 3-1-1=1$ . Otherwise, WLOG, assume $f_3\left(v_i\right)\ge 4$ . Then $f_{5^{+}}\left(v_{i+1}\right)\ge 2$ by the choice of G, we have

$c\left(v_{i+1}\to f_i\right)\ge \left(4-2\times \frac{1}{4}\right)/3=\frac{7}{6}$ ,

so $c\left(v\to f_i\right)\le 3-\frac{4}{5}-\frac{7}{6}\mathrm{<mo>=</mo>}\frac{31}{30}$ . Since $\max \left\{\mathrm{1,}\frac{31}{30}\right\}=\frac{31}{30}$ , $c\left(v\to f_i\right)\le \frac{31}{30}$ . $\square$

Now, we begin to show that $c{h}^{\prime }\left(v\right)\ge 0$ for 6-vertex $v$ . Note that $f_b\left(v\right)$ is 0 or 1 by Lemma 7, $f_3\left(v\right)\le 4$ by the choice of G. In terms of $f_3\left(v\right)$ , there are the following four cases.

Case 1. $f_3\left(v\right)\le 1$ . Note that $v$ transfers at most $\frac{13}{8}$ to each 3-face incident with $v$ by Lemma 8, at most $\frac{3}{4}$ to each 4⁺-face incident with $v$ by R1 and R2. So $c{h}^{\prime }\left(v\right)\ge 6-f_3\left(v\right)\times \frac{13}{8}-\left(6-f_3\left(v\right)\right)\times \frac{3}{4}\mathrm{<mo>=</mo>}\frac{3}{2}-\frac{7}{8}{f}_3\left(v\right)>0$ .

Case 2. $f_3\left(v\right)=2$ . If $f_b\left(v\right)=1$ , then another 3-face is a $\left(5^{+}{\mathrm{,5}}^{+}\mathrm{,6}\right)$ -triangle by Lemma 7, it follows that $c{h}^{\prime }\left(v\right)\ge 6-\frac{13}{8}-\frac{31}{30}-4\times \frac{3}{4}=\frac{41}{120}>0$ . Otherwise, $f_b\left(v\right)=0$ , then $v$ transfers at most $\frac{5}{4}$ to each 3-face incident with $v$ by Lemma 8 and R2. Hence, $c{h}^{\prime }\left(v\right)\ge 6-2\times \frac{5}{4}-4\times \frac{3}{4}=\frac{1}{2}>0$ .

Case 3. $f_3\left(v\right)=3$ . If $f_b\left(v\right)=1$ , then

$c{h}^{\prime }\left(v\right)\ge 6-\frac{13}{8}-2\times \frac{31}{30}-3\times \frac{3}{4}=\frac{7}{120}>0$ .

Otherwise, $f_b\left(v\right)=0$ , we have $c{h}^{\prime }\left(v\right)\ge 6-3\times \frac{5}{4}-3\times \frac{3}{4}=0$ .

Case 4. $f_3\left(v\right)=4$ . Note that either $f_4\left(v\right)=f_{6^{+}}\left(v\right)=1$ or $f_{5^{+}}\left(v\right)=2$ . If $f_b\left(v\right)=1$ , then $c{h}^{\prime }\left(v\right)\ge 6-\frac{13}{8}-3\times \frac{31}{30}-\max \left\{\frac{3}{4},2\times \frac{1}{4}\right\}=\frac{21}{40}>0$ . Otherwise, $f_b\left(v\right)=0$ , we have $c{h}^{\prime }\left(v\right)\ge 6-4\times \frac{5}{4}-\max \left\{\frac{3}{4},2\times \frac{1}{4}\right\}=\frac{1}{4}>0$ .

3. Conclusion

In conclusion, the proof of the Theorem 2 is now complete.

Acknowledgements

This work was supported by the Science and Technology Research Project of Higher Education Institutions in Inner Mongolia Autonomous Region (Grant Nos. NJZY22599, NJZY22600), the Key Laboratory of Infinite-dimensional Hamiltonian System and Its Algorithm Application (Inner Mongolia Normal University), Ministry of Education (Grant Nos. 2023KFZR01, 2023KFZR02), the Fundamental Research Funds for the Inner Mongolia Normal University (Grant No. 2022JBTD007).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. North-Holland.
[2]	Behzad, M. (1965) Graphs and Their Chromatic Numbers. PhD Thesis, Michigan State University.
[3]	Vizing, V.G. (1968) Some Unsolved Problems in Graph Theory. Uspekhi Matematicheskikh Nauk, 23, 117-134. (In Russian)
[4]	Rosenfeld, M. (1971) On the Total Coloring of Certain Graphs. Israel Journal of Mathematics, 9, 396-402. https://doi.org/10.1007/bf02771690
[5]	Vijayaditya, N. (1971) On Total Chromatic Number of a Graph. Journal of the London Mathematical Society, 2, 405-408. https://doi.org/10.1112/jlms/s2-3.3.405
[6]	Kostochka, A.V. (1977) The Total Coloring of a Multigraph with Maximal Degree 4. Discrete Mathematics, 17, 161-163. https://doi.org/10.1016/0012-365x(77)90146-7
[7]	Kostochka, A.V. (1996) The Total Chromatic Number of Any Multigraph with Maximum Degree Five Is at Most Seven. Discrete Mathematics, 162, 199-214. https://doi.org/10.1016/0012-365x(95)00286-6
[8]	Sanders, D.P. and Zhao, Y. (1999) On Total 9-Coloring Planar Graphs of Maximum Degree Seven. Journal of Graph Theory, 31, 67-73. https://doi.org/10.1002/(sici)1097-0118(199905)31:1<67::aid-jgt6>3.0.co;2-c
[9]	Yap, H.P. (1996) Total Colourings of Graphs. Lectures Notes in Mathematics 1623. Springer.
[10]	Sun, X., Wu, J., Wu, Y. and Hou, J. (2009) Total Colorings of Planar Graphs without Adjacent Triangles. Discrete Mathematics, 309, 202-206. https://doi.org/10.1016/j.disc.2007.12.071
[11]	Hou, J.F., Liu, G.Z., Xin, Y.X. and Lan, M. (2008) Some Results on Total Colorings of Planar Graphs. Journal of Applied Mathematics and Informatics, 26, 511-517.
[12]	Roussel, N. (2011) Local Condition for Planar Graphs of Maximum Degree 6 to Be Total 8-Colorable. Taiwanese Journal of Mathematics, 15, 87-99. https://doi.org/10.11650/twjm/1500406163
[13]	Leidner, M. (2013) A Larger Family of Planar Graphs That Satisfy the Total Coloring Conjecture. Graphs and Combinatorics, 30, 377-388. https://doi.org/10.1007/s00373-012-1278-4
[14]	Zhu, E. and Xu, J. (2017) A Sufficient Condition for Planar Graphs with Maximum Degree 6 to Be Totally 8-Colorable. Discrete Applied Mathematics, 223, 148-153. https://doi.org/10.1016/j.dam.2017.01.036
[15]	Liang, Z. (2020) Total Coloring of Claw-Free Planar Graphs. Discussiones Mathematicae Graph Theory, 42, 771-777. https://doi.org/10.7151/dmgt.2300
[16]	Zhou, Y., Zhao, D., Ma, M. and Xu, J. (2022) Total Coloring of Recursive Maximal Planar Graphs. Theoretical Computer Science, 909, 12-18. https://doi.org/10.1016/j.tcs.2022.01.024
[17]	Shen, L. and Wang, Y. (2009) On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-Cycles. Graphs and Combinatorics, 25, 401-407. https://doi.org/10.1007/s00373-009-0843-y
[18]	Borodin, O.V. (1989) On the Total Coloring of Planar Graphs. Journal fur die Reine und Angewandte Mathematik, 394, 180-185.
[19]	Kowalik, L., Sereni, J. and Škrekovski, R. (2008) Total-Coloring of Plane Graphs with Maximum Degree Nine. SIAM Journal on Discrete Mathematics, 22, 1462-1479. https://doi.org/10.1137/070688389
[20]	Roussel, N. and Zhu, X. (2010) Total Coloring of Planar Graphs of Maximum Degree Eight. Information Processing Letters, 110, 321-324. https://doi.org/10.1016/j.ipl.2010.02.012
[21]	Chang, G.J., Hou, J. and Roussel, N. (2011) Local Condition for Planar Graphs of Maximum Degree 7 to Be 8-Totally Colorable. Discrete Applied Mathematics, 159, 760-768. https://doi.org/10.1016/j.dam.2011.01.001
[22]	Wang, B. and Wu, J. (2012) Total Colorings of Planar Graphs without Intersecting 5-Cycles. Discrete Applied Mathematics, 160, 1815-1821. https://doi.org/10.1016/j.dam.2012.03.027
[23]	Chang, J., Wang, H., Wu, J. and A, Y. (2013) Total Colorings of Planar Graphs with Maximum Degree 8 and without 5-Cycles with Two Chords. Theoretical Computer Science, 476, 16-23. https://doi.org/10.1016/j.tcs.2013.01.015
[24]	Chang, J., Wu, J., Wang, H. and Guo, Z. (2014) Total Colorings of $F_5$-Free Planar Graphs with Maximum Degree 8. The Electronic Journal of Combinatorics, 21, 1-15. https://doi.org/10.37236/3303
[25]	Xu, R. and Wu, J. (2014) Total Coloring of Planar Graphs with 7-Cycles Containing at Most Two Chords. Theoretical Computer Science, 520, 124-129. https://doi.org/10.1016/j.tcs.2013.08.019
[26]	Cai, H. (2015) Total Coloring of Planar Graphs without Chordal 7-Cycles. Acta Mathematica Sinica, English Series, 31, 1951-1962. https://doi.org/10.1007/s10114-015-4337-y
[27]	Wang, H., Liu, B. and Wu, J. (2014) Total Coloring of Planar Graphs without Chordal Short Cycles. Graphs and Combinatorics, 31, 1755-1764. https://doi.org/10.1007/s00373-014-1449-6
[28]	Cai, H., Wu, J. and Sun, L. (2015) Total Coloring of Planar Graphs without Short Cycles. Journal of Combinatorial Optimization, 31, 1650-1664. https://doi.org/10.1007/s10878-015-9859-9
[29]	Wang, H.J., Luo, Z.Y., Liu, B., Gu, Y. and Gao, H.W. (2016) A Note on the Minimum Total Coloring of Planar Graphs. Acta Mathematica Sinica, English Series, 32, 967-974. https://doi.org/10.1007/s10114-016-5427-1
[30]	Wang, L., Wang, H. and Wu, W. (2023) Minimum Total Coloring of Planar Graphs with Maximum Degree 8. Journal of Combinatorial Optimization, 45, Article No. 82. https://doi.org/10.1007/s10878-023-01011-y