A proper total coloring of a graph \( G \) such that there are at least 4 colors on those vertices and edges incident with a cycle of \( G \), is called an acyclic total coloring. The acyclic total chromatic number of \( G \), denoted by \( \chi^{”}_{a}(G) \), is the smallest number of colors such that \( G \) has an acyclic total coloring. In this article, we prove that for any graph \( G \) with \( \Delta(G)=\Delta \) which satisfies \( \chi^{”}(G)\leq A \) for some constant \( A \), and for any integer \( r \), \( 1\leq r \leq 2\Delta \), there exists a constant \( c>0 \) such that if \( g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r} \), then \( \chi^{”}_{a}(G)\leq A+r \).
In this paper, all graphs considered are finite and undirected. Let \(G=(V,E)\) be a graph, where \(V=V(G)\) and \(E=E(G)\) are the vertex set and the edge set of \(G\), respectively [6]. We use \(\Delta(G)\), \(\delta(G)\) to denote the maximum degree and the minimum degree of a graph \(G\), respectively. The girth of a graph \(G\), denoted by \(g(G)\), is the length of the shortest cycle in \(G\). As usual, [k] stands for the set \(\{1,2,\ldots, k\}\).
A proper vertex (or edge) \(k\)-coloring of a graph \(G\) is a mapping \(\varphi\) from \(V(G)\) (or \(E(G)\)) to the color set [k] such that no pair of adjacent vertices (or adjacent edges) are colored with the same color. A proper vertex (or edge) coloring of a graph \(G\) is called acyclic if there is no \(2\)-chromatic cycle (cycle colored with precisely two colors) in \(G\), i.e., the union of any two color classes induces a forest in \(G\). The acyclic chromatic number of \(G\), denoted by \(\chi_{a}(G)\), is the smallest number \(k\) of colors such that \(G\) has an acyclic \(k\)-coloring. The acyclic chromatic index of \(G\), denoted by \(\chi^{'}_{a}(G)\), is the smallest number \(k\) of colors such that \(G\) has an acyclic edge \(k\)-coloring.
The concept of acyclic coloring of a graph was introduced by Grünbaum [14] who conjecture that every planar graph is acyclically \(5\)-colorable, which was proved by Borodin [7]. In 2011, Kostochka et al. [21] proved that every graph with maximum degree 5 has an acyclic \(7\)-coloring, i.e., \(\chi_{a}(G)\leq7\). In 2014, Zhao and Miao et al. [31] proved that every graph with maximum degree \(6\) is acyclically \(10\)-colorable, i.e., \(\chi_{a}(G)\leq10\).
In 2001, Alon et al. [2] proposed the Acyclic Edge Coloring Conjecture, which states that for every graph \(G\), \(\chi^{'}_{a}(G)\leq\Delta(G)+2\). This conjecture was justified for several classes of graphs, including non-regular graphs with maximum degree at most 4 [4], subcubic graphs [3,26], outerplanar graphs [17,23], series-parallel graphs [16], planar graphs without small cycles [15,16], etc. In 2010, Borowiecki et al. [11] proved the conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4, 6, 8 and 9. They also show that \(\chi^{'}_{a}(G)\leq\Delta(G)+1\) if \(G\) is planar with girth at least 6. In 2012, Lin et al. [22] proved that for a graph \(G\) with maximum degree \(\Delta\) and girth \(g(G)\), and for any integer \(r\) with \(1\leq r \leq 2\Delta\), there exists a constant \(c>0\) such that if \(g(G)\geq\frac{c\Delta}{r} \log(\frac{\Delta^{2}}{r})\), then \(\chi^{'}_{a}(G)\leq \Delta+r+1\).
A proper total \(k\)-coloring of a graph \(G\) is a mapping \(\phi:E(G)\cup V(G)\rightarrow\{1,2,\ldots,k\}\) such that no two adjacent or incident elements receive the same color. The total chromatic number of \(G\), \(\chi^{''}(G)\), is the smallest integer \(k\) such that \(G\) has a proper total \(k\)-coloring. An acyclic total \(k\)-coloring is a proper total \(k\)-coloring of a graph \(G\) such that there are at least 4 colors on those vertices and edges incident with a cycle of \(G\). The acyclic total chromatic number of \(G\), denoted by \(\chi^{''}_{a}(G)\), is the smallest number \(k\) of colors such that \(G\) has an acyclic total \(k\)-coloring.
Behzad [5] and Vizing [29] independently conjectured that \(\Delta(G)+1\leq\chi^{''}(G)\leq\Delta(G)+2\) (the Total Coloring Conjecture). In 1971, Rosenfeld [24] proved that if \(G\) is a graph with \(\Delta(G)\leq3\), then \(\chi^{''}(G)\leq5\). In 1977, Kostochka [19] proved that if \(G\) is any multigraph with \(\Delta(G)\leq4\), then \(\chi^{''}(G)\leq6\). In 1996, Kostochka [20] proved that for each multigraph \(G\) with \(\Delta(G)\leq5\), \(\chi^{''}(G)\leq7\). Borodin [8] proved that every planar graph with \(\Delta(G)\geq9\) is total \((\Delta(G)+2)\)-colorable. This result was improved to the case \(\Delta(G)\geq8\) by employing Four-Color Theorem and Vizing’s Theorem on the edge coloring [18]. More recently, Sanders and Zhao [25] further settled the \(\Delta(G)=7\) case. For planar graphs, the Total Coloring Conjecture remains open only for the \(\Delta(G)=6\) case. It was shown that \(\chi^{''}(G)=\Delta(G)+1\) if \(G\) is a planar graph with \(\Delta(G)\geq14\) [8], with \(\Delta(G)\geq12\) [9], with \(\Delta(G)=11\) [10] and with \(\Delta(G)=10\) [30].
The acyclic total coloring was introduced by Sun and Wu [28], who proved that the acyclic total chromatic number of a planar graph \(G\) is at most \(\Delta(G)+2\) if \(\Delta(G)\geq12\), or if \(\Delta(G)\geq6\) and \(g(G) \geq4\), or if \(\Delta(G)\geq5\) and \(g(G) \geq5\), or if \(g(G) \geq6\). Furthermore, they proved that \(\chi^{''}_{a}(G)=\Delta(G)+1\) if \(G\) is a series-parallel graph with \(\Delta(G)\geq3\). They also showed in the same paper that \(\chi^{''}_{a}(G) \leq\Delta(G)+2\) for a bipartite graph \(G\). Lastly, they posed the following conjucture.
Conjecture 1.1. \(\Delta(G)+1 \leq \chi^{''}_{a}(G) \leq \Delta(G)+2\) for any graph \(G\).
For a planar graph \(G\) of maximum degree at least \(k\) and without \(l\) cycles, the conjecture is proved to be true if \((k,l)\in\{(6,3),(7,4),(6,5),(7,6)\}\) [27]. For every plane graph \(G\), \(\chi^{''}_{a}(G)=\Delta(G)+1\) if \(\Delta(G)\geq9\) and \(g(G)\geq4\), or if \(\Delta(G)\geq6\) and \(g(G)\geq5\), or if \(\Delta(G)\geq4\) and \(g(G)\geq6\), or if \(\Delta(G)\geq3\) and \(g(G)\geq14\) [12].
To the best of our knowledge, there are not many results on the bounds of the acyclic total chromatic number. In this paper, we investigate the acyclic total coloring of graphs with large girths, and prove the following theorem.
Theorem 1.2. For any graph \(G\) with \(\Delta(G)=\Delta\) which satisfies \(\chi^{''}(G)\leq A\) for some constant \(A\), and for any integer \(r\), \(1\leq r \leq 2\Delta\), there exists a constant \(c>0\) such that if \(g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r}\), then \(\chi^{''}_{a}(G)\leq A+r\).
Corollary 1.3. For any graph \(G\) with \(\Delta(G)=\Delta\) which satisfies \(\chi^{''}(G)=\Delta+1\), and for any integer \(r\), \(1\leq r \leq 2\Delta\), there exists a constant \(c>0\) such that if \(g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r}\), then \(\chi^{''}_{a}(G)\leq \Delta+r+1\).
Thus, for \(r=1\) such graphs also satisfy Conjecture 1.1.
Corollary 1.4. For any graph \(G\) with \(\Delta(G)=\Delta\) which satisfies \(\chi^{''}(G)=\Delta+2\), and for any integer \(r\), \(1\leq r \leq 2\Delta\), there exists a constant \(c>0\) such that if \(g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r}\), then \(\chi^{''}_{a}(G)\leq \Delta+r+2\).
In Section 2, we give some preliminaries, including the definitions, symbols and conclusions used in this paper. We then give the proof of the main result in Section 3.
A cycle is a graph such that each its vertex is of degree two. The length of a cycle is the number of its edges. A cycle of length \(k\) is called a \(k\)-cycle. A half-edge contains a vertex and one of its incident edges.
Lemma 2.1. [28] If \(G\) is a cycle, then \(\chi^{''}_{a}(G)=4\).
The proof of Theorem 1.2 relies heavily on the following general form of the Lovász local lemma [1,13].
Lemma 2.2. Let \(A_{1},A_{2},\ldots,A_{n}\) be the random events, and suppose that there exist real numbers \(x_{1},x_{2},\ldots,x_{n}\) such that \(0<x_{i}<1,i=1,2,\ldots,n\), and \[\text{Pr}(A_{i})\leq x_{i} \prod_{\{ i,j \}\in E(D)}(1-x_{j}). \label{eq2.1} \tag{1}\]
Then Pr\((\bigcap^{n}_{i=1}\overline{A_{i}})>0\).
The graph \(D\) involved in the lemma above is called dependency graph. The vertex set \(V(D)\) consists of all events \(A_{i}\), in which every event \(A_{i}\) is mutually independent of all \(A_{j}\) with \(\{i,j\} \not \in E(D)\).
The technique used in the proof is similar to that in [22].
In the following, we will prove the theorem by showing that if \(g(G)\geq\frac{c\Delta}{r} \log(\frac{\Delta^{2}}{r})\), then there exists an acyclic total coloring of \(G\) with \(A+r\) colors. Without loss of generality, we suppose that the graph \(G\) is connected.
If \(\Delta=0\), namely \(G\) is a trivial graph, then \(\chi^{''}_{a}(G)=1\).
If \(\Delta=1\), namely \(G\) is an edge, then \(\chi^{''}_{a}(G)=3\).
If \(\Delta=2\), then \(G\) is a path, a parallel edge or a cycle. If \(G\) is a path, then \(\chi^{''}_{a}(G)=3\). If \(G\) is a parallel edge, then \(\chi^{''}_{a}(G)=4\). Otherwise, \(\chi^{''}_{a}(G)=4\) by Lemma 2.1.
So we can suppose that \(\Delta\geq3\). The proof consists of two steps. First, since \(\chi^{''}(G)\leq A\), we can properly color the vertices and edges of \(G\) by \(A\) colors. Let \(c\) denote this total coloring. Next, each vertex and each edge is recolored with the remaining \(r\) colors randomly and independently with probability \(p_{1}\), \(p_{2}\), respectively. Let us denote the set of those remaining \(r\) colors by \([r]=\{1,2,\ldots,r\}\). Now, it suffices to show that with positive probability:
\((A)\) the total coloring remains proper: no two adjacent or incident elements are colored with color \(i\) for some \(i\in[r]\), and
\((B)\) the total coloring becomes acyclic: every cycle of \(G\) contains at least four different colors. To assume that \((A)\) and \((B)\) hold, we need only to avoid the following six types of “bad” events.
Type 1.For each pair of adjacent vertices \(L=\{v_{1},v_{2}\}\), let \(E_{L}\) be the event that both \(v_{1}\) and \(v_{2}\) are recolored with \(i\) for some \(i\in[r]\).
Type 2.For each pair of adjacent edges \(C=\{e_{1},e_{2}\}\), let \(E_{C}\) be the event that both \(e_{1}\) and \(e_{2}\) are recolored with \(i\) for some \(i\in[r]\).
Type 3.For each half-edge \(D=\{v_{1},e_{1}\}\), let \(E_{D}\) be the event that both \(v_{1}\) and \(e_{1}\) are recolored with \(i\) for some \(i\in[r]\).
Type 4.For each \(3k\)-cycle \(F\) which has three colors in the first total coloring, let \(E_{F}\) be the event that both of \(V(F)\) and \(E(F)\) are not recolored.
For each \(3k\)-cycle \(H=v_{0}e_{1}v_{1}e_{2}v_{2}\cdots e_{3k-1}v_{3k-1}e_{3k}v_{0}=x_{1}x_{2}\cdots x_{6k-1}x_{6k}x_{1}\). We mark \(O=\{x_{1},x_{4},\ldots,x_{6k-2}\}\), \(P=\{x_{2},x_{5},\ldots,x_{6k-1}\}\), \(Q=\{x_{3},x_{6},\ldots,x_{6k}\}\). After the first total coloring \(c\) in \(G\), a \(3k\)-cycle \(H\) is called partial-monochromatic if at least one of the sets \(O\), \(P\), \(Q\) is monochromatic. Note that this includes cycles which contain three colors by the first total coloring.
Type 5. For each partial-monochromatic \(3k\)-cycle \(H\) in the first total coloring, let \(E_{H}\) denote the event that at least \(\frac{1}{3}\) of the vertices and edges of \(H\) are recolored such that \(H\) is properly total \(3\)-chromatic in the new total coloring.
Type 6.For each \(3k\)-cycle \(J\) which is not a partial-monochromatic cycle in the first total coloring, let \(E_{J}\) be the event that \(J\) is properly total \(3\)-chromatic in the new total coloring.
We claim that if no events of Types 1-6 appear, then \((A)\) and \((B)\) hold. It is easy to see that \((A)\) holds if no events of Types 1, 2 or 3 appear. Since total colorings of \((3k+1)\)-cycles and \((3k+2)\)-cycles are acyclic, only \(3k\)-cycles can be 3-chromatic in the new total coloring. If no element of such the \(3k\)-cycle was recolored with some new color, then the cycle would be of Type 4. Otherwise, if the \(3k\)-cycle was recolored, then such the cycle would be either partial-monochromatic and consequently of Type 5 or non-partial-monochromatic and consequently of Type 6. Thus \((B)\) holds if no elements of Types 4, 5 or 6 appear. Thus it suffices to show that none of these events occur with positive probability, namely, the probability that both \((A)\) and \((B)\) hold is positive. Now, let \(K\) be the dependency graph whose vertex set consists of all the events of the six types, in which two vertices \(E_{X}\) and \(E_{Y}\) (\(X,Y\in\{L,C,D,F,H,J\}\)) are adjacent if and only if \(X\) and \(Y\) share a common vertex or a common edge. It is immediate that the probabilities of the above six types are as follows.
1) Pr\((E_{L})=rp^{2}_{1}\) for each event \(E_{L}\) of Type 1.
2) Pr\((E_{C})=rp^{2}_{2}\) for each event \(E_{C}\) of Type 2.
3) Pr\((E_{D})=rp_{1}p_{2}\) for each event \(E_{D}\) of Type 3.
4) Pr\((E_{F})=(1-rp_{1})^{3x}(1-rp_{2})^{3x}\) for each event \(E_{F}\) of Type 4, where \(F\) is of length \(3x\).
5) Pr\((E_{H})\leq 3\binom{r}{1}p_{1}^{x}p_{2}^{x}\) for each event \(E_{H}\) of Type 5, where \(H\) is of length \(3x\).
6) Pr\((E_{J})\leq 3!\binom{r}{3}p_{1}^{3x}p_{2}^{3x}\) for each event \(E_{J}\) of Type 6, where \(J\) is of length \(3x\).
In order to apply the Lovász local lemma, we also need to estimate the degrees of vertices of each type in \(K\).
Lemma 3.1. For any given vertex \(v\) in \(G\), we have that
(1)at most \(\Delta\) vertices are adjacent to \(v\);
(2)at most \(\Delta\) half-edges contain \(v\);
(3)at most \(\Delta\) \(3k\)-cycles which are properly total \(3\)-chromatic contain \(v\);
(4)fewer than \(\Delta^{2k}\) partial-monochromatic \(3k\)-cycles contain \(v\);
(5)fewer than \(\Delta^{3k-1}\) \(3k\)-cycles contain \(v\).
Proof. It is obvious that (1), (2) hold. To prove (3), we find a total 3-chromatic \(3k\)-cycle \(H=ve_{1}v_{1}e_{2}v_{2}\cdots e_{3k-1}v_{3k-1}e_{3k}v\) as follows. For vertex \(v\) in \(G\), select an edge \(e_{1}\) which is incident to \(v\) (at most \(\Delta\) possibilities). We use \(v_{1}\) to denote the other endpoint of \(e_{1}\). Then, select an edge \(e_{2}\) which is adjacent to \(e_{1}\) such that \(c(e_{2})=c(v)\) and \(c(v_{2})=c(e_{1})\), where \(v_{2}\) is the other endpoint of \(e_{2}\). There is at most one such edge \(e_{2}\) since the total coloring \(c\) is proper. If such a vertex \(v_{2}\) does not exist, the number of cycles is smaller than the bound presented in the lemma. Then, for \(i=2,3,\ldots,3k\), there is at most one possible edge \(e_{i}\) such that the \(3k\)-cycle \(H\) is total 3-chromatic. Therefore the number of \(3k\)-cycles which are properly total \(3\)-chromatic that contain vertex \(v\) is at most \(\Delta\).
To prove (4), we find a partial-monochromatic \(3k\)-cycle \(M=ve_{1}v_{1}e_{2}v_{2} \cdots e_{3k-1}v_{3k-1}e_{3k}v\\=x_{1}x_{2}\cdots x_{6k-1}x_{6k}x_{1}\) (without loss of generality, we assume that \(v=x_{1}\) and \(Q\) is monochromatic, since other cases are similar) as follows. Select an edge \(x_{2}\) which is incident to \(x_{1}\) (at most \(\Delta\) possibilities). Next, select an edge \(x_{4}\) which is adjacent to \(x_{2}\) (at most \(\Delta-1\) possibilities). Then, select an edge \(x_{6}\) which is adjacent to \(x_{4}\) such that \(c(x_{6})=c(x_{3})\). There is at most one such edge \(x_{6}\) since the total coloring \(c\) is proper. If such an edge does not exist, the number of cycles is smaller than the bound presented in the lemma. Next, we proceed similarly. For \(i=2,\ldots,k\), we select in turn the edge \(x_{6i-4}\) (at most \(\Delta-1\) possibilities), \(x_{6i-2}\) (at most \(\Delta-1\) possibilities) and \(x_{6i}\) such that \(c(x_{6i})=c(x_{6i-3})\) (at most one possibility). Therefore the number of partial-monochromatic \(3k\)-cycles that contain \(v\) is fewer than \(\Delta^{2k}\).
To prove (5), we find a \(3k\)-cycle \(N=ve_{1}v_{1}e_{2}v_{2}\cdots e_{3k-1}v_{3k-1}e_{3k}v\) as follows. For vertex \(v\) in \(G\), select an edge \(e_{1}\) which is incident to \(v\) (at most \(\Delta\) possibilities). Next, for \(i=2,\ldots,3k-1\), there are at most \(\Delta-1\) possible edges \(e_{i}\) and at most one possible edges \(e_{3k}\) such that \(N\) is a \(3k\)-cycle. Therefore the number of \(3k\)-cycles that contain vertex \(v\) is fewer than \(\Delta^{3k-1}\).
This completes the proof of Lemma 3.1. ◻
Lemma 3.2. For any given edge \(e\) in \(G\), we have that
(1)fewer than \(2\Delta\) edges are adjacent to \(e\);
(2)exactly two half-edges contain \(e\);
(3)exactly one \(3k\)-cycle which is properly total \(3\)-chromatic contains \(e\);
(4)fewer than \(2\Delta^{2k-1}\) partial-monochromatic \(3k\)-cycles contain \(e\);
(5)fewer than \(2\Delta^{3k-2}\) \(3k\)-cycles contain \(e\).
Proof. It is obvious that (1), (2), (3) hold.
To prove (4), we find a partial-monochromatic \(3k\)-cycle \(M=v_{0}ev_{1}e_{2}v_{2} \cdots e_{3k-1}v_{3k-1}e_{3k}v_{0}=x_{1}x_{2}\cdots x_{6k-1}x_{6k}x_{1}\) (without loss of generality, we assume that \(e=x_{2}\) and \(P\) is monochromatic, since other cases are similar) as follows. Select an edge \(x_{4}\) which is adjacent to \(x_{2}\) such that \(c(x_{5})=c(x_{2})\) (at most \(2(\Delta-1)\) possibilities). Next, for \(i=2,\ldots,k\), we select in turn the edge \(x_{6i-6}\) which is adjacent to \(x_{6i-8}\) (at most \(\Delta-1\) possibilities), \(x_{6i-4}\) which is adjacent to \(x_{6i-6}\) such that \(c(x_{6i-4}) = c(x_{6i-7})\) (at most one possibility), and \(x_{6i-2}\) which is adjacent to \(x_{6i-4}\) such that \(c(x_{6i-1}) = c(x_{6i-4})\) (at most \(\Delta-1\) possibilities). Finally, there is at most one possible edge \(x_{6k}\), for all \(k\), such that \(M\) is a partial-monochromatic \(3k\)-cycle. Therefore the number of partial-monochromatic \(3k\)-cycles that contain \(e\) is fewer than \(2\Delta^{2k-1}\).
To prove (5), we find a \(3k\)-cycle \(N=v_{0}ev_{1}e_{2}v_{2}\cdots e_{3k-1}v_{3k-1}e_{3k}v_{0}\) as follows. For edge \(e\) in \(G\), select an edge \(e_{2}\) which is adjacent to \(e\) (at most \(2(\Delta-1)\) possibilities). Then, for \(i=3,\ldots,3k-1\), there are at most \(\Delta-1\) possible edges \(e_{i}\) and at most one possible edge \(e_{3k}\) such that \(N\) is a \(3k\)-cycle. Therefore the number of \(3k\)-cycles that contain edge \(e\) is fewer than \(2\Delta^{3k-2}\).
This completes the proof of Lemma 3.2. ◻
It follows from Lemma 3.1 and Lemma 3.2 that each event \(E_{X}\), where \(X\) contains \(x\) vertices and \(y\) edges, is adjacent (in the dependency graph \(K\)) to
(1)at most \(\Delta x\) events of Type 1;
(2)at most \(2\Delta y\) events of Type 2;
(3)at most \(\Delta x\) events of Type 3;
(4)at most \(\Delta x+y\) events of Type 4;
(5)at most \((\Delta x+2y)\Delta^{2k-1}\) events of Type 5, for all \(k\geq1\);
(6)at most \((\Delta x+2y)\Delta^{3k-2}\) events of Type 6, for all \(k\geq1\).
Now, we shall check that (1) holds for all events. To this end, let us put
\[p_{1}= p_{2}=\frac{1}{32\Delta}, g=g(G)\geq855\frac{\Delta}{r}\log\frac{\Delta^{2}}{r} ,\]
\[x_{1}=x_{2}=x_{3}=\frac{r}{512\Delta^{2}},\] for Type 1, 2, 3, respectively,
\[x_{4}=\frac{r}{512\Delta^{2}},\] with \(3k\)-cycle for Type 4,
\[x_{5}=\frac{r}{\Delta(2\Delta)^{2k}},\] with \(3k\)-cycle for Type 5,
\[x_{6}=\frac{r}{(2\Delta)^{3k}} ,\] with \(3k\)-cycle for Type 6 .
It remains to show that the following inequalities hold. \[\label{3.1} \begin{aligned} \text{Pr}(E_{L})=rp^{2}_{1}\leq & x_{1}(1-x_{1})^{2\Delta}(1-x_{3})^{2\Delta}(1-x_{4})^{2\Delta}\prod_{k\geq\frac{g}{3}}(1-x_{5})^{2\Delta^{2k}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{2\Delta^{3k-1}}, \end{aligned} \tag{2}\] \[\label{3.2} \begin{aligned} \text{Pr}(E_{C})=rp^{2}_{2}\leq x_{2}(1-x_{2})^{4\Delta}(1-x_{4})^{2}\prod_{k\geq\frac{g}{3}}(1-x_{5})^{4\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{4\Delta^{3k-2}}, \end{aligned} \tag{3}\] \[\label{3.3} \begin{aligned} \text{Pr}(E_{D})=rp_{1}p_{2}\leq &x_{3}(1-x_{1})^{\Delta}(1-x_{2})^{2\Delta}(1-x_{3})^{\Delta}(1-x_{4})^{\Delta+1}\\ &\prod_{k\geq\frac{g}{3}}(1-x_{5})^{(\Delta+2)\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{(\Delta+2)\Delta^{3k-2}}, \end{aligned} \tag{4}\] \[\label{3.4} \begin{aligned} \text{Pr}(E_{F}) =&(1-rp_{1})^{3x}(1-rp_{2})^{3x} \leq x_{4}(1-x_{1})^{3x\Delta}(1-x_{2})^{6x\Delta}(1-x_{3})^{3x\Delta}(1-x_{4})^{3x(\Delta+1)}\\ &\prod_{k\geq\frac{g}{3}}(1-x_{5})^{3x(\Delta+2)\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{3x(\Delta+2)\Delta^{3k-2}}, \text{for all } x\geq \frac{g}{3}, \end{aligned} \tag{5}\] \[\label{3.5} \begin{aligned} \text{Pr}(E_{H}) \leq &3\binom{r}{1}p_{1}^{x}p_{2}^{x} \leq x_{5}(1-x_{1})^{3x\Delta}(1-x_{2})^{6x\Delta}(1-x_{3})^{3x\Delta}(1-x_{4})^{3x(\Delta+1)}\\ &\prod_{k\geq\frac{g}{3}}(1-x_{5})^{3x(\Delta+2)\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{3x(\Delta+2)\Delta^{3k-2}}, \text{for all } x\geq \frac{g}{3}, \end{aligned} \tag{6}\] \[\label{3.6} \begin{aligned} \text{Pr}(E_{J}) \leq &3!\binom{r}{3}p_{1}^{3x}p_{2}^{3x} \leq x_{6}(1-x_{1})^{3x\Delta}(1-x_{2})^{6x\Delta}(1-x_{3})^{3x\Delta}(1-x_{4})^{3x(\Delta+1)}\\ &\prod_{k\geq\frac{g}{3}}(1-x_{5})^{3x(\Delta+2)\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{3x(\Delta+2)\Delta^{3k-2}}, \text{for all } x\geq \frac{g}{3}. \end{aligned} \tag{7}\]
Remark 3.3. If \(r\leq2\), then there is no Type 6 and all \[\prod_{k\geq\frac{g}{3}}(1-x_{6})^{3x(\Delta+2)\Delta^{3k-2}},\] above shall be deleted.
Since \((1-\frac{1}{a})^{a}\geq\frac{1}{4}\) for all \(a\geq2\), we have \[\prod_{k\geq\frac{g}{3}}(1-x_{5})^{\Delta^{2k}}\geq\prod_{k\geq\frac{g}{3}}\left(\frac{1}{4}\right)^{\frac{r}{2^{2k}\Delta}}=\left(\frac{1}{4}\right)^{\frac{r}{\Delta}\sum_{k\geq\frac{g}{3}}\frac{1}{2^{2k}}}\geq\left(\frac{1}{4}\right)^{\frac{r}{2^{\frac{2g}{3}-1}\Delta}},\] \[\prod_{k\geq\frac{g}{3}}(1-x_{5})^{\Delta^{2k-1}}\geq\prod_{k\geq\frac{g}{3}}\left(\frac{1}{4}\right)^{\frac{r}{2^{2k}\Delta^{2}}}=\left(\frac{1}{4}\right)^{\frac{r}{\Delta^{2}}\sum_{k\geq\frac{g}{3}}\frac{1}{2^{2k}}}\geq\left(\frac{1}{4}\right)^{\frac{r}{2^{\frac{2g}{3}-1}\Delta^{2}}},\] \[\prod_{k\geq\frac{g}{3}}(1-x_{6})^{\Delta^{3k-1}}\geq\prod_{k\geq\frac{g}{3}}\left(\frac{1}{4}\right)^{\frac{r}{2^{3k}\Delta}}=\left(\frac{1}{4}\right)^{\frac{r}{\Delta}\sum_{k\geq\frac{g}{3}}\frac{1}{2^{3k}}}\geq\left(\frac{1}{4}\right)^{\frac{r}{2^{g-1}\Delta}},\] \[\prod_{k\geq\frac{g}{3}}(1-x_{6})^{\Delta^{3k-2}}\geq\prod_{k\geq\frac{g}{3}}\left(\frac{1}{4}\right)^{\frac{r}{2^{3k}\Delta^{2}}}=\left(\frac{1}{4}\right)^{\frac{r}{\Delta^{2}}\sum_{k\geq\frac{g}{3}}\frac{1}{2^{3k}}}\geq\left(\frac{1}{4}\right)^{\frac{r}{2^{g-1}\Delta^{2}}}.\]
Noting that \(r\leq2\Delta\) and \(g\geq855\frac{\Delta}{r}\log\frac{\Delta^{2}}{r}>32\), we have that
\[(1-x_{1})^{2\Delta}(1-x_{3})^{2\Delta}(1-x_{4})^{2\Delta}\prod_{k\geq\frac{g}{3}}(1-x_{5})^{2\Delta^{2k}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{2\Delta^{3k-1}}\] is at least
\[\label{3.7} \left(\frac{1}{4}\right)^{\frac{3r}{256\Delta}+\frac{2r}{2^{\frac{2g}{3}-1}\Delta}+\frac{2r}{2^{g-1}\Delta}}\geq\left(\frac{1}{2}\right)^{\frac{r}{32\Delta}}>\frac{1}{2}, \tag{8}\] which implies that (2) hold. Similarly,
\[\label{3.8} \begin{aligned} (1-x_{2})^{4\Delta}(1-x_{4})^{2}\prod_{k\geq\frac{g}{3}}(1-x_{5})^{4\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{4\Delta^{3k-2}} \geq&\left(\frac{1}{4}\right)^{\frac{r}{128\Delta}+\frac{r}{256\Delta^{2}}+\frac{4r}{2^{\frac{2g}{3}-1}\Delta^{2}}+\frac{4r}{2^{g-1}\Delta^{2}}}\\ \geq&\left(\frac{1}{2}\right)^{\frac{r}{32\Delta}}>\frac{1}{2}, \end{aligned} \tag{9}\]
\[\label{3.9} \begin{aligned} &(1-x_{1})^{\Delta}(1-x_{2})^{2\Delta}(1-x_{3})^{\Delta}(1-x_{4})^{\Delta+1}\prod_{k\geq\frac{g}{3}}(1-x_{5})^{(\Delta+2)\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{(\Delta+2)\Delta^{3k-2}} \\&\geq \left(\frac{1}{4}\right)^{\frac{r}{128\Delta}+\frac{r(\Delta+1)}{512\Delta^{2}}+\frac{r(\Delta+2)}{2^{\frac{2g}{3}-1}\Delta^{2}}+\frac{r(\Delta+2)}{2^{g-1}\Delta^{2}}} \\&\geq \left(\frac{1}{4}\right)^{\frac{r}{128\Delta}+\frac{r}{256\Delta}+\frac{2r}{2^{\frac{2g}{3}-1}\Delta}+\frac{2r}{2^{g-1}\Delta}} \\&\geq \left(\frac{1}{2}\right)^{\frac{r}{32\Delta}}>\frac{1}{2}. \end{aligned} \tag{10}\]
Eqs. (3) and (4) hold.
In order to prove inequality (5) , it suffices to show that \[\label{3.10} e^{-\frac{3rx}{16\Delta}}<\frac{r}{512\Delta^{2}}\left(\frac{1}{2}\right)^{\frac{3rx}{16\Delta}}, \tag{11}\] by \((1-rp)^{x}\leq e^{-rpx}\) for all \(x>0\). It is immediate that \((3.10)\) holds since \(x\geq \frac{g}{3}\geq\frac{855\Delta}{3r}\log\frac{\Delta^{2}}{r}>\frac{16\Delta\log\frac{512\Delta^{2}}{r}}{3r\log\frac{e}{2}}\) and \(\Delta\geq3\).
Using (10) we have \[\label{3.11} \begin{aligned} &(1-x_{1})^{3x\Delta}(1-x_{2})^{6x\Delta}(1-x_{3})^{3x\Delta}(1-x_{4})^{3x(\Delta+1)}\\&\prod_{k\geq\frac{g}{3}}(1-x_{5})^{3x(\Delta+2)\Delta^{2k-1}}\prod_{k\geq\frac{g}{3}}(1-x_{6})^{3x(\Delta+2)\Delta^{3k-2}}\geq \left(\frac{1}{2}\right)^{\frac{3xr}{32\Delta}}>\left(\frac{1}{2}\right)^{x}. \end{aligned} \tag{12}\]
It is immediate that (6) holds since \(\frac{128^{x}}{3}\geq\frac{128^{\frac{855\Delta}{3r}\log\frac{\Delta^{2}}{r}}}{3}\geq\frac{1}{3}\left(\frac{128}{e}\right)^{\frac{855}{6}\log\frac{\Delta}{2}} \left(\frac{\Delta}{2}\right)^{\frac{855}{6}}>\Delta\). Noting that \(r-1, r-2\leq2\Delta\), we have that \[\label{3.12} \begin{aligned} 3!\binom{r}{3}p_{1}^{3x}p_{2}^{3x}=\frac{r(r-1)(r-2)}{(32\Delta)^{6x}}\leq\frac{4\Delta^{2}r}{(32\Delta)^{6x}}, \end{aligned} \tag{13}\] which implies that (7) holds. This completes the proof of Theorem 1.2.
This work was supported by the National Natural Science Foundation of China (NO. 11771443). The authors would like to express their gratitude to the referees for their careful reading and very useful suggestions, which greatly improved the quality of this paper.