Graph coloring is one of the chief topics in graph research. The graph coloring was applied to chemistry, biology, VLSI, etc., see [1, 2], It is well known to compute the chromatic number of graphs is NP-Hard in graphs theory. In the past, the people had some results about it by combination methods, see [3, 4, 5, 6, 7]. In 1974, Edrös proved $r(k,k)\geq 2^{\frac{k}{2}}$ by probability. At ICM2002, Noga Alon had a report about the method and challenge of Discrete mathematics. The viewpoint that the problem of graph coloring studied by probability drew the field of graph attention. For instance, some conclusions was gotten by probability methods. In [8], Alon proved that $\alpha'(G) \leq \Delta +2$ for any graph whose girth is at least $2000\Delta\log\Delta$, where $\Delta$ is maximum degree of $G$. In [9], Rahul Muthu et al. improved the result of [8]. In [10], Hamed Hatami proved that if $\Delta > 10^{20}$, then $\chi_{as}(G) < \Delta +300$, where $\Delta(G)$ is maximum degree of $G$. In 2006, Zhang Zhongfu and Akbaria presented the concept of the $r$-strong edge coloring independently, see [11, 12]. When $r=2$, the $r$-strong edge-chromatic number is denoted by $\chi{'}_{s}(G,2)$. Let $\Delta$ be the maximum degree of $G$. In this paper, we study the upper bound for the the $r$-strong edge chromatic number of regular graph by probability method, prove that if $3\leq \Delta \leq 730$, then $\chi{'}_{s}(G,2)\leq 2\Delta+1$ by the general local lemma. All the graphs $G=G(V,E)$ discussed in this paper are finite, undirected, simple and connected.

Definition 2.1  A proper edge coloring of a graph $G$ is a map $f: E(G) \rightarrow C$, where $C$ is a set of colors such that no two edges with the same colors are incident with the same vertex, see[3].

Definition 2.2  For a graph $G(V, E)$, if a proper $k$-edge coloring $f$ is satisfied with $S(u)\neq S(v)$ for $uv \in E(G)$, where $S(u) =\{f(uv)|uv\in E\}$, then $f$ is called $k$-adjacent Vertex-distinguishing edge coloring of $G$, is abbreviated $k$-ASEC, and

$\chi{'}_{as}(G)= \min\{k|k {\rm - ASEC of} G \}$

is called the adjacent Vertex-distinguishing edge chromatic number of $G$, see [4].

Definition 2.3  For any $u, v \in V(G), d(u, v)$ denotes the distance between $u$ and $v$ and $N(v)$ denotes the set of all vertices adjacent to vertex $v$. A proper edge coloring of a graph $G$ is called an $r$-strong edge coloring if for any two distinct vertices $u, v \in V(G)$ with $d(u, v) \leq r$, we have $S(u) \neq S(v)$. The $r$-strong edge coloring number $ \chi{'}_{s}(G, r)$ is the minimum number of colors required for an $r$-strong edge coloring of the graph $G$, see [11, 12].

Obviously, $\chi{'}_{s}(G,1)=\chi{'}_{as}$when $r=1$, $\chi{'}_{s}(G,r)=\chi{'}_{s}$ when $r \geq \mbox{Diam}(G)$, where $\mbox{diam}(G)$ is the diameter of the graph.

Definition 2.4  Let $A_1, A_2, \ldots, A_n$ be events in an arbitrary probability space. A directed graph $D=(V, E)$ on the set of vertices $V=\{1, 2, \cdots, n\}$ is called a dependency digraph for the events $A_1, A_2, \cdots, A_n$ if for each $i, 1\leq i\leq n$, the event $A_i$ is mutually independent of all the events $\{A_j:(i, j)\overline{\in }E \}$, see [13, 14].

Lemma 2.2  (the general local lemma) Consider a set $\varepsilon =\{A_1, A_2, \ldots, A_n\}$ of (typically bad) events such that each $A_i$ is mutually independent of $\varepsilon -(D_i \cup A_i)$ for some $D_i\subseteq \varepsilon$. If there exist $x_1, x_2, \ldots, x_n \in [0, 1]$ such that for each $1\leq i\leq n$,

$\Pr(A_i)\leq x_i \prod\limits _{A_j \in D_i}(1-x_j), $

then the probability that none of the events in $\varepsilon$ occurs is at least

$ \prod\limits _{i=1}^{n}(1-x_i)> 0,$

see [13, 14]

Theorem 2.3  If $G(V,E)$ has $2\leq \Delta \leq 730 $, then $\chi_{s}'(G,2)\leq 2\Delta+1$.

Proof  By Vizing theorem, it is possible to color all edges of $G$ by $\Delta+1$ colors properly, so we have proper edge coloring $f_{0}$. And then each of edges in $G$ is recolored randomly and independently with an equal probability $\frac{1}{16(\Delta)^{\frac{3}{2}}}$ to one of $\Delta$ new colors, name this edge coloring of $G$ as $g$. We will use Lemma 1 to show that a positive probability, $g$ is $2$-strong edge coloring. In order to show that, the following conditions should be satisfied:

$[1]$ The coloring is proper-no pair of adjacent edges are colored with the same color;

$[2]$ The coloring is adjacent-vertex-distinguishing-no pair of adjacent vertices meet the same color set;

$[3]$ No pair of vertices whose distance is $2$ meet the same color set.

Step 1 The following bad events are defined in order to satisfy above:

(1) For each pair of adjacent edges $e,f$, let $A_{e,f}$ be the event that both $e$ and$f$ are colored with the same color;

(2) For each edge $e=uw$, such that ${\rm deg}(u)={\rm deg}(w)$, let$B_e$ be the set of all edges which are connected $u$ or $w$, then $E_{B_{e}}$ be the event that the edges which are adjacent to $u$ and $w$ are colored properly, and $S(u)=S(w)$;

(3) For each path whose length is $2$, $P_{uv}=uewfv$, 令such that deg$(u)=$deg$(v)$, let $P_{uv}$ be the set of all edges which are incident with $u$ or $v$, then $E_{P_{uv}}$ is the event that the edgs which are incident with $u$ and $v$ are colored properly, and $S(u)= S(v)$.

It remains to show that with positive probability none of these events happen, then $G$ has a $2$ -strong edge-coloring. To prove this we apply the local lemma. Let us construct dependency graph $H$ whose nodes are all the events of two nodes $E_{X}$ and $E_{Y}$ (where each of $X$ and $Y$ is either a pair of incident edges, or the set of all edges that are adjacent to an edge together with that edge itself, or the set of all edges incident to two vertices $u$ and $v$ which distance is $2$) are adjacent if and only if $X$ and $Y$ contain at least one common edge. Since the occurrence of each event $E_{X}$ depends only on the edges of $X,H$ is dependency graph for our events. In order to apply the general local lemma, we need estimates for the probability of each event and the number of nodes of each type in $H$ which are adjacent to any give node. These estimates are given in the two steps below.

Step 2 Estimate the probability of each event: If $A_{e,f}$ occurs, then $e,f$ in $A_{e,f}$ are recolored with the same color. So

$\begin{eqnarray*}&& \Pr(A_{e,f})={\Delta \choose 1}(\frac{1}{16\Delta^{\frac{3}{2 }}})^2=\frac{1}{16^2\Delta^{2}}, \\ && \Pr(E_{P_{uv}})=[{\Delta \choose 1}(\frac{1}{16\Delta^{\frac{3}{2 }}})^\Delta+{\Delta \choose 2}(\frac{1}{2\cdot16\Delta^{\frac{3}{2 }}})^\Delta+\cdots+{\Delta \choose \Delta-1}(\frac{1}{(\Delta-1)16\Delta^{\frac{3}{2 }}})^\Delta]^2\\ &\leq& [{\Delta \choose 1}+{\Delta \choose 2}+\cdots+{\Delta \choose \Delta-1}]^2[(\frac{1}{16\Delta^{\frac{3}{2 }}})^\Delta]^2\\ &\leq& [2^\Delta (\frac{1}{16\Delta^\frac{3}{2}})^\Delta]^2 = \frac{1}{(64\Delta^3)^\Delta}. \end{eqnarray*}$

Let $e=uv, {\rm deg}(u)={\rm deg}(v)=\Delta$, if $E_{B_{e}}$ occurs, then edges in$B_{e}$ are colored properly and $S(u)= S(v)$, namely, $S(u)-\{f(e)\}=S(v)-\{f(e)\}=S.$ Assume $S$ is a fixed set which has $i$ member of the new colors and $\Delta-i$ members of the old colors. With probability $(1-\frac{1}{8}{\Delta})$ preserves its previous color. This event happens with the probability of

$\begin{eqnarray*}&& [i!(1-\frac{1}{8}{\Delta})^{\Delta-i}(\frac{1}{16\Delta^{\frac{3}{2}}})^i]^2 \leq [i^{i}\exp(\frac{8}{\Delta}(i-\Delta))(\frac{1}{16\Delta^{\frac{3}{2}}})^i]^2\\ &=& i^{2i}\exp(\frac{16}{\Delta}(i))\exp(\frac{16}{\Delta}(-\Delta))(\frac{1}{16\Delta^{\frac{3}{2}}})^{2i} = (\frac{i^{2}\exp(\frac{16}{\Delta})}{16^2\Delta^2})^i\exp(-16), \end{eqnarray*}$

$\begin{eqnarray*}&& Pr(E_{B_{e}})\leq\sum\limits_{i=0}^{\Delta}{\Delta \choose i}{\Delta \choose i}(\frac{i^{2}\exp(\frac{16}{\Delta})}{16^2\Delta^2})^i\exp(-16)\\ &\leq& \sum\limits_{i=0}^{\Delta}(\frac{e\Delta}{i}\frac{e\Delta}{i} \frac{i^{2}\exp(\frac{16}{\Delta})}{16^2\Delta^2})^i\exp(-16) \leq\exp(-16).\end{eqnarray*}$

Step 3 Estimate the dependency events number, in the following table:

For the dependency events numbers in the table, we have some explanations. For each event $A_{e, f}$ of Type $\langle1\rangle$, the corresponding vertex of $A_{e, f}$ in $H$ is adjacent to at most $4\Delta-5$ events of type $\langle 1\rangle$. This is because that each edge $e$ and $f$ is adjacent to at most $2\Delta-2$ (except for $e$ itself) edge, there are two edge $e$ and $f$ in event of type $\langle 1\rangle$, $e, f$ are adjacent to at most $2\cdot(2\Delta-2)=4\Delta-4$, the edge adjacent to $e$ (or $f$) contains $f$ (or $e$), the set $\{e, f\}$ is compute twice, so the result is $2\cdot(2\Delta-2)-1=4\Delta-5$. For each event $A_{e, f}$ of type $\langle 2\rangle$, the corresponding vertex of $A_{e, f}$ in $H$ is adjacent to at most $3\Delta-2$ events of type $\langle 2\rangle$. This is because that each vertex is adjacent to at most $\Delta$ vertices, there are three vertices in type $\langle 2\rangle$, except the common vertex $u$ of $e$ and $f$, another terminate vertex $u_1$ of $e$ and another terminate vertex $u_2$ of $f$ are compute twice, so the result is $3\cdot \Delta -2=3\Delta-2$. The others can be explained similarly.

Step 4 Find the real constant $x_i(0\leq x_i\leq 1)$ for applying Lemma 3. Let $\frac{2}{16^2\Delta^2},\ \frac{1}{8\Delta^2},\frac{2}{(64\Delta^3)^\Delta}$ be the constants associated with events of types $(1)$, $ (2)$, $ (3)$.

Step 5 Conclude that with positive probability no events of type $(1)$, $ (2)$, $ (3), $ provided that

$\begin{eqnarray}&& \frac{1}{16^2\Delta^2} \leq\ {\frac{2}{16^2\Delta^2}\ (1-\frac{2}{16^2\Delta^2})^{4\Delta-5}\ (1-\frac{2}{(64\Delta^3)^\Delta})^{\Delta(\Delta-1)+2(\Delta-1)^2}\ (1-\frac{1}{8\Delta^2})^{3\Delta-2}}, \end{eqnarray}$

(2.1)

$\begin{eqnarray} \exp(-16)\leq\frac{1}{8\Delta^2}(1-\frac{2}{16^2\Delta^2})^{(2\Delta-1)(2\Delta-2)}\ (1-\frac{1}{8\Delta^2})^{(2\Delta-2)\Delta+1}\ (1-\frac{2}{(64\Delta^3)^{\Delta}})^{(2\Delta-1)\Delta(\Delta-1)},\nonumber \end{eqnarray}$

(2.2)

$\begin{eqnarray} && \frac{1}{(64\Delta^3)^\Delta} \leq\ \frac{2}{(64\Delta^3)^\Delta}\ (1-\frac{2}{16^2\Delta^2})^{2\Delta(2\Delta-1)+1+2(\Delta-2)}\ (1-\frac{1}{8\Delta^2})^{2\Delta^2+\Delta-2}\nonumber\\ && (1-\frac{2}{(64\Delta^3)^{\Delta}})^{2(\Delta-1)^3+\Delta(\Delta-1)}. \end{eqnarray}$

(2.3)

Now since $(1-\frac{1}{z})^{z}\geq \frac{1}{4},$ to prove (2.1), it suffices to prove the following inequality:

$\frac{1}{2} \leq (\frac{1}{2})^{(4\Delta-5)+\frac{3\Delta-2}{4\Delta^2}+\frac{4[\Delta(\Delta-1)+2(\Delta-1)^2]}{(64\Delta^3)^{\Delta}}}.$

(2.1*)

In order to proof $(2.1*)$, it is only to prove

$1\geq \frac{(4\Delta-5)}{64\Delta^2}+\frac{3\Delta-2}{4\Delta^2}+\frac{4(\Delta-1)(3\Delta-2)}{(64\Delta^3)^{\Delta}}, $

(2.1**)

when$\Delta >2$, inequality $(2.1**)$ is true, thus the inequality is hold(2.1), in order to prove (2.2), it is only need to prove

$\begin{aligned}& \exp(-16)\leq \exp(-\ln(8\Delta^2))\exp(\frac{-4(2\Delta-1)(2\Delta-2)}{16^2\Delta^2})\\ & \exp(\frac{-2[(2\Delta-2)\Delta+1]}{8\Delta^2})\exp (\frac{-4(2\Delta-1)\Delta(\Delta-1)}{(64\Delta^3)^{\Delta}}), \end{aligned}$

(2.2*)

in order to prove $(2*)$, it is only need to prove

$-16 \leq -\ln(8\Delta^2)-\frac{-4(2\Delta-1)(2\Delta-2)}{16^2\Delta^2} -\frac{-2[(2\Delta-2)\Delta+1]}{8\Delta^2}- \frac{-4(2\Delta-1)\Delta(\Delta-1)}{(64\Delta^3)^{\Delta}}, $

(2.2**)

when $\Delta \leq 730$, inequality $(2.2**)$ is true, thus inequality (2.2) is hold.

Now since $(1-\frac{1}{z})^{z}\geq \frac{1}{4}, $ to prove (2.3), it suffices to prove the following inequality.

In order to prove (2.3), it is only need to prove

$\frac{1}{2}\leq (\frac{1}{2})^{\frac{(4\Delta^2-3)}{16^2\Delta^2}+\frac{2\Delta^2+\Delta-2}{4\Delta^2}+\frac{4(\Delta-1)(2\Delta^2-3\Delta+2)}{(64\Delta^3)^{\Delta}}}. $

(2.3*)

In order to prove$(2.3*)$, it is only need to prove

$1\geq \frac{(4\Delta^2-3)}{16^2\Delta^2}+\frac{2\Delta^2+\Delta-2}{4\Delta^2}+\frac{4(\Delta-1)(2\Delta^2-3\Delta+2)}{(64\Delta^3)^{\Delta}}, $

(2.3**)

when$\Delta\geq 2$, inequality $(2.3**)$is true, thus inequality (2.3) is hold.

Above all, $G$ has $2\Delta+1-\chi{'}_{s}(G,2)$. This complete the proof