# Proving a conjecture on the upper bound of semistrong chromatic indices of
graphs

Yuquan Lin and Wensong Lin111Corresponding author. E-mail address:
<EMAIL_ADDRESS>
School of Mathematics, Southeast University, Nanjing 210096, P.R. China

###### Abstract

Let $G=(V(G),E(G))$ be a graph with maximum degree $\Delta$. For a subset $M$
of $E(G)$, we denote by $G[V(M)]$ the subgraph of $G$ induced by the
endvertices of edges in $M$. We call $M$ a semistrong matching if each edge of
$M$ is incident with a vertex that is of degree 1 in $G[V(M)]$. Given a
positive integer $k$, a semistrong $k$-edge-coloring of $G$ is an edge
coloring using at most $k$ colors in which each color class is a semistrong
matching of $G$. The semistrong chromatic index of $G$, denoted by
$\chi^{\prime}_{ss}(G)$, is the minimum integer $k$ such that $G$ has a
semistrong $k$-edge-coloring. Recently, Lužar, Mockovčiaková and Soták
conjectured that $\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$ for any connected
graph $G$ except the complete bipartite graph $K_{\Delta,\Delta}$. In this
paper, we settle this conjecture by proving that each such graph $G$ other
than a cycle on $7$ vertices has a semistrong edge coloring using at most
$\Delta^{2}-1$ colors.

Keywords: strong matching; semistrong matching; strong edge coloring;
semistrong edge coloring; $(0,1)$-relaxed strong edge coloring.

##  1 Introduction

Let $G=(V(G),E(G))$ be a finite undirected simple graph. For $v\in V(G)$, let
$N(v)=\\{u\in V(G):uv\in E(G)\\}$ denote the open neighborhood of $v$ and
$d(v)=|N(v)|$ be the degree of $v$. Let $\Delta=\max\limits_{v\in V(G)}d(v)$
denote the maximum degree of $G$. For $M\subseteq E(G)$, we denote by
$G[V(M)]$ the subgraph of $G$ induced by the endvertices of edges in $M$.

Given two positive integers $i$ and $j$. Denote by $C_{i}$ the cycle on $i$
vertices. And denote by $K_{i,j}$ the complete graph with two parts of sizes
$i$ and $j$, respectively. For convenience, we use the abbreviation $[1,i]$
for $\\{1,2,\dots,i\\}$.

Let $e$ and $e^{\prime}$ be two edges of $G$. If $e$ and $e^{\prime}$ are
adjacent to each other, we say that the distance between $e$ and $e^{\prime}$
is $1$, and if they are not adjacent but both of them are adjacent to a common
edge, we say they are at distance $2$. An induced matching (also called a
strong matching) $M$ of $G$ is a matching such that no two edges of $M$ are at
distance $1$ or $2$ in $G$. In other words, a matching $M$ of $G$ is induced
if each vertex in $G[V(M)]$ is of degree 1.

Given a positive integer $k$, a strong $k$-edge-coloring of $G$ is an
assignment of $k$ colors to the edges of $G$ such that each color class is an
induced matching. The strong chromatic index of $G$, denoted by
$\chi^{\prime}_{s}(G)$, is the minimum integer $k$ such that $G$ has a strong
$k$-edge-coloring.

The concept of strong edge coloring, first introduced by Fouquet and Jolivet
[9], can be used to model the conflict-free channel assignment problem in
radio networks [19, 18]. In 1985, Erdős and Nešetřil [6, 7] proposed the
following conjecture about the upper bound of $\chi^{\prime}_{s}(G)$ in terms
of $\Delta$, which if true, is the best possible.

###### Conjecture 1.1

$($Erdős and Nešetřil [6, 7]$)$ If $G$ is a graph with maximum degree
$\Delta$, then

$\chi^{\prime}_{s}(G)\leq\begin{cases}\begin{array}[]{cl}\dfrac{5}{4}\Delta^{2},&\text{if}\
\Delta\ \text{is even,}\\\
\dfrac{5}{4}\Delta^{2}-\dfrac{1}{2}\Delta+\dfrac{1}{4},&\text{if}\ \Delta\
\text{is odd.}\end{array}\end{cases}$

This conjecture is probably one of the most important conjectures in the study
of strong edge coloring. In recent decades, many pieces of research on strong
edge coloring have been carried out based on this conjecture. However, not
much progress has been made in proving it directly. Only the case $\Delta\leq
3$ was confirmed completely by Andersen [1] in 1992, and independently by
Horák, Qing, and Trotter [14] in 1993. Apart from that, the problem is widely
open.

For sufficiently large $\Delta$, Molloy and Reed [17] first proved that
$\chi^{\prime}_{s}(G)\leq 1.998\Delta^{2}$ by using probabilistic techniques
in 1997. This bound was improved to $1.93\Delta^{2}$ by Bruhn and Joos [4] in
2015 and was further strengthened to $1.835\Delta^{2}$ by Bonamy, Perrett and
Postle [3] in 2022. The current best known upper bound is $1.772\Delta^{2}$
which was shown by Hurley, de Joannis de Verclos and Kang [15] in 2021. These
results mentioned above apply a similar proof method, but this method has its
limitations, so the best possible coefficient by far is still not very close
to the objective of 1.25.

It seems difficult to prove Conjecture 1.1 directly. Recently, a lot of
attention has been paid to various variants of strong edge coloring (see,
e.g., [2, 10, 11, 12, 13]). In 2005, the concept of semistrong edge coloring
was introduced by Gyárfás and Hubenko [11]. They weakened the notion of strong
(induced) matching and introduced the semistrong matching. A semistrong
matching $M$ of $G$ is an edge subset such that each edge of $M$ is incident
with a vertex that is of degree 1 in $G[V(M)]$.

Naturally, given a positive integer $k$, a semistrong $k$-edge-coloring of $G$
is an edge coloring using at most $k$ colors in which each color class is a
semistrong matching of $G$. The minimum integer $k$ such that $G$ has a
semistrong $k$-edge-coloring is called the semistrong chromatic index of $G$,
denoted by $\chi^{\prime}_{ss}(G)$. It is clear that
$\chi^{\prime}_{ss}(G)\leq\chi^{\prime}_{s}(G)$. In [11], the authors showed
that if $G$ is a Kneser graph or a subset graph, then
$\chi^{\prime}_{ss}(G)=\chi^{\prime}_{s}(G)$.

Lužar, Mockovčiaková and Soták [16] revived the semistrong edge coloring and
further explored its properties. They indicated that the complete graphs and
the complete bipartite graphs are two other families of graphs with the same
value of strong and semistrong chromatic indices. And they revealed the fact
that, according to the work of Diwan [5] and the work of Faudree, Schelp,
Gyárfás and Tuza [8], it can be concluded that
$\chi^{\prime}_{ss}(Q^{n})=\chi^{\prime}_{s}(Q^{n})=2n$ for any
$n$-dimensional cube $Q^{n}$ with $n\geq 2$.

In [16], the authors also proved that $\chi^{\prime}_{ss}(G)\leq\Delta^{2}$
for every graph $G$ with maximum degree $\Delta$. Moreover, for the case
$\Delta=3$, they improved the bound 9 to 8 for every connected graph $G$ that
is not isomorphic to $K_{3,3}$, where the $5$-prism (as shown in Figure 2)
shows the sharpness of the upper bound 8. At the end of their paper, they
proposed the following conjecture.

###### Conjecture 1.2

$($Lužar, Mockovčiaková, Soták [16]$)$ For every connected graph $G$ with
maximum degree $\Delta$, distinct from $K_{\Delta,\Delta}$, it holds that
$\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$.

This paper settles this conjecture by proving the following two theorems.

###### Theorem 1.3

Let $G$ be a graph with maximum degree $2$. If no component of $G$ is
isomorphic to $C_{4}$ or $C_{7}$, then $\chi^{\prime}_{ss}(G)\leq 3$.

###### Theorem 1.4

Let $G$ be a graph with maximum degree $\Delta\geq 3$. If no component of $G$
is isomorphic to $K_{\Delta,\Delta}$, then
$\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$.

It should be pointed out that different relaxations of strong edge coloring
may be related to each other. For example, the $(s,t)$-relaxed strong edge
coloring, which was first proposed by He and Lin [12] in 2017, is suitable for
the channel assignment problem with limited channel resources in wireless
radio networks. For any nonnegative integers $s,t$ and $k$, an $(s,t)$-relaxed
strong $k$-edge-coloring of $G$ is an assignment of $k$ colors to edges of
$G$, such that for each edge $e$ of $G$, at most $s$ edges at distance 1 and
at most $t$ edges at distance 2 from $e$ receive the same color as $e$. The
$(s,t)$-relaxed strong chromatic index of $G$, denoted by
$\chi^{\prime}_{(s,t)}(G)$, is the minimum integer $k$ such that $G$ admits an
$(s,t)$-relaxed strong $k$-edge-coloring.

In [12], He and Lin studied the $(s,t)$-relaxed strong edge coloring of trees
and constructed a $(0,\Delta-1)$-relaxed strong $(\Delta+1)$-edge-coloring for
any given tree $T$ with maximum degree $\Delta$. Then in [16], the authors
pointed out that such a coloring provided by He and Lin is also a semistrong
edge coloring, which implies that $\chi^{\prime}_{ss}(T)\leq\Delta+1$ for any
tree $T$. Moreover, they also proved in [16] that for any graph $G$, there
exists an edge coloring using at most $\Delta^{2}$ colors that is both a
semistrong edge coloring and a $(0,1)$-relaxed strong edge coloring. In other
words, for any graph $G$ with maximum degree $\Delta$,
$\chi^{\prime}_{(0,1)}(G)\leq\Delta^{2}$.

Inspired by their work in [16], in solving Conjecture 1.2, we construct an
edge coloring which is both a semistrong edge coloring and a $(0,1)$-relaxed
strong edge coloring, and thus we also prove the following.

###### Theorem 1.5

For any connected graph $G$ with maximum degree $\Delta\geq 2$, distinct from
$C_{7}$, we have $\chi^{\prime}_{(0,1)}(G)\leq\Delta^{2}-1$.

Remark 1. The semistrong chromatic index and the $(s,t)$-relaxed strong
chromatic index of a graph $G$ are not comparable. For instance, for the cycle
$C_{4}$, $\chi^{\prime}_{ss}(C_{4})=4>\chi^{\prime}_{(0,1)}(C_{4})=2$. And for
the cycle $C_{7}$, it holds that
$\chi^{\prime}_{ss}(C_{7})=\chi^{\prime}_{(0,1)}(C_{7})=4$. While for the
graph $T_{0}$ in Figure 2,
$\chi^{\prime}_{ss}(T_{0})=3<\chi^{\prime}_{(0,1)}(T_{0})=4$.

Figure 1: The graph $5$-prism

Figure 2: The graph $T_{0}$

Remark 2. For the strong chromatic index of a graph $G$, the upper bound in
Conjecture 1.1 is $1.25\Delta^{2}$, and the current best result for large
$\Delta$ is $1.772\Delta^{2}$ provided by Hurley, de Joannis de Verclos and
Kang [15]. While our bounds of both the semistrong chromatic index and the
$(0,1)$-relaxed strong chromatic index are $\Delta^{2}-1$. This implies that,
a little relaxation can save a large proportion of colors.

The remainder of this paper is dedicated to the proof of Theorems 1.3, 1.4 and
1.5. It is organized as follows. In Section 2, we deal with the case that the
maximum degree of $G$ is $2$ and the case that $G$ is isomorphic to
$K_{\Delta,\Delta}$, respectively. In the next two sections, we assume that
$G$ is a graph with maximum degree $\Delta\geq 3$ and no component of $G$ is
isomorphic to $K_{\Delta,\Delta}$. In Section 3, after stating some
definitions and notation, we introduce some auxiliary results that will play a
crucial role in the proof that follows. Section 4 is the main body of the
proof. Finally, we summarize our results and suggest some future research
directions in Section 5.

##  2 The proofs of two special cases

Let $G$ be a connected graph with maximum degree $\Delta$. In this section, we
consider the semistrong chromatic index and the $(0,1)$-relaxed strong
chromatic index of $G$ when $\Delta=2$ and when $G$ is isomorphic to
$K_{\Delta,\Delta}$, respectively.

Notice that all edges of $C_{4}$ must receive different colors in any
semistrong edge coloring, $\chi^{\prime}_{ss}(C_{4})=4$. And it is obvious
that $\chi^{\prime}_{(0,1)}(C_{4})=2$. Notice also that a semistrong matching
of $C_{7}$ consists of at most two edges, $\chi^{\prime}_{ss}(C_{7})\geq 4$.
And a semistrong edge coloring of $C_{7}$ using $4$ colors is easy to get.
Therefore, $\chi^{\prime}_{ss}(C_{7})=4$. Similarly, it is easy to see that
$\chi^{\prime}_{(0,1)}(C_{7})=4$.

###### Lemma 2.1

Let $G$ be a connected graph with maximum degree $2$. If $G$ is not isomorphic
to $C_{4}$ or $C_{7}$, then $\chi^{\prime}_{ss}(G)\leq 3$ and
$\chi^{\prime}_{(0,1)}(G)\leq 3$.

Proof. Let $G$ be a connected graph with maximum degree $2$. Then $G$ is
either a path or a cycle. If $G$ is a path with $n$ vertices, without loss of
generality, label the vertices of $G$ as $v_{1},v_{2},\ldots,v_{n}$ and the
edges $e_{i}=v_{i}v_{i+1}$ for $i=1,2,\ldots,n-1$. Now let $\phi(e_{i})=i\bmod
3$ for each $i\in[1,n-1]$. This yields an edge coloring $\phi$ of $G$ using at
most 3 colors which is both semistrong and $(0,1)$-relaxed strong.

Next we suppose that $G$ is a cycle $C_{n}=v_{1}v_{2}\ldots v_{n}$ with $n\geq
3$ and $n\notin\\{4,7\\}$. Denote the edge $v_{i}v_{i+1}$ by $e_{i}$ for each
$i\in[1,n-1]$ and the edge $v_{n}v_{1}$ by $e_{n}$. Now, if $n\equiv 1(\bmod\
3)$, let $\phi(e_{i})=i\bmod 3$ for each $i\in[1,n-4]$, and let
$\phi(e_{n-3})=2$, $\phi(e_{n-2})=1$, $\phi(e_{n-1})=0$ and $\phi(e_{n})=2$.
Otherwise, let $\phi(e_{i})=i\bmod 3$ for each $i\in[1,n]$. It is easy to
check that, in both cases, we obtain a semistrong edge coloring $\phi$ of $G$
using 3 colors which is also a $(0,1)$-relaxed strong edge coloring.
Therefore, Lemma 2.1 is proved.

Theorem 1.3 follows directly from Lemma 2.1.

###### Lemma 2.2

$\chi^{\prime}_{ss}(K_{\Delta,\Delta})=\Delta^{2}$ and
$\chi^{\prime}_{(0,1)}(K_{\Delta,\Delta})=\lceil\frac{\Delta^{2}}{2}\rceil$.

Proof. Recall that all edges of $C_{4}$ must receive different colors in any
semistrong edge coloring, all edges in $K_{\Delta,\Delta}$ must receive
different colors in any semistrong edge coloring of it and thus
$\chi^{\prime}_{ss}(K_{\Delta,\Delta})=\Delta^{2}$.

Now we prove that
$\chi^{\prime}_{(0,1)}(K_{\Delta,\Delta})=\lceil\frac{\Delta^{2}}{2}\rceil$.
On the one hand, notice that any two edges of $K_{\Delta,\Delta}$ are at
distance 1 or 2, each color class of a $(0,1)$-relaxed strong edge coloring of
$K_{\Delta,\Delta}$ consists of at most two edges, and thus
$\chi^{\prime}_{(0,1)}(K_{\Delta,\Delta})\geq\lceil\frac{\Delta^{2}}{2}\rceil$.
On the other hand, denote the two partitions of $K_{\Delta,\Delta}$ by
$U=\\{u_{1},u_{2},\ldots,u_{\Delta}\\}$ and
$V=\\{v_{1},v_{2},\ldots,v_{\Delta}\\}$, respectively. Then let
$\phi(u_{i}v_{j})=\phi(u_{j}v_{i})=\alpha_{i,j}$ for any two different
integers $i,j\in[1,\Delta]$, and let
$\phi(u_{i}v_{i})=\beta_{\lceil\frac{i}{2}\rceil}$ for each $i\in[1,\Delta]$.
It is clear that $\phi$ is a $(0,1)$-relaxed strong edge coloring using
$\tbinom{\Delta}{2}+\lceil\frac{\Delta}{2}\rceil=\lceil\frac{\Delta^{2}}{2}\rceil$
colors, and so
$\chi^{\prime}_{(0,1)}(K_{\Delta,\Delta})\leq\lceil\frac{\Delta^{2}}{2}\rceil$.
Therefore, the lemma is proved.

Due to Lemmas 2.1 and 2.2, we can complete the proofs of Theorems 1.4 and 1.5
by proving the following theorem.

###### Theorem 2.3

Let $G$ be a graph with maximum degree $\Delta\geq 3$. If no component of $G$
is isomorphic to $K_{\Delta,\Delta}$, then
$\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$ and
$\chi^{\prime}_{(0,1)}(G)\leq\Delta^{2}-1$.

In the following, we concentrate on proving Theorem 2.3.

##  3 Preliminaries and notation

In this section, we introduce some notation and preliminary facts that we will
use in our proofs. We ususlly use $\alpha$, $\beta$, $\gamma$ to denote colors
and $\phi$, $\psi$, $\sigma$ to denote edge colorings. And we sometimes simply
write “coloring” instead of “edge coloring”.

Let $G$ be a graph. Given an edge coloring $\phi$ of $G$. For $S\subseteq
E(G)$, we denote by $\phi(S)$ the set of colors assigned to the edges in $S$
under $\phi$.

For any two edges $e,f\in E(G)$, we say that $f$ is a $1$-neighbor (resp.
$2$-neighbor) of $e$ if $f$ and $e$ are at distance 1 (resp. 2), and $f$ is a
$2^{-}$-neighbor of $e$ if they are at distance 1 or 2. For any $e\in E(G)$,
we use $C_{e}^{\Delta}$ to denote the set of $1$-neighbors of $e$ lying on a
common $3$-cycle with $e$.

For each edge $e=uv\in E(G)$, we denote by $N(e)$ (resp. $N^{2}(e)$) the set
of $1$-neighbors (resp. $2$-neighbors) of $e$, and by $N^{2-}(e)$ the set of
$2^{-}$-neighbors of $e$. It is obvious that $N(e)\cap N^{2}(e)=\emptyset$ and
$N^{2-}(e)=N(e)\cup N^{2}(e)$. Let $N[e]=N(e)\cup\\{e\\}$ and
$N^{2-}[e]=N^{2-}(e)\cup\\{e\\}$. Similarly, let $N_{u}(e)$ denote the set of
$1$-neighbors of $e$ having $u$ as an endvertex and $N_{u}^{2}(e)$ the set of
$2$-neighbors of $e$ being adjacent to some edge in $N_{u}(e)$. And denote by
$N_{u}^{2-}(e)$ the set of edges in $N_{u}(e)$ or $N_{u}^{2}(e)$. Moreover,
let $N_{u}[e]=N_{u}(e)\cup\\{e\\}$ and
$N_{u}^{2-}[e]=N_{u}^{2-}(e)\cup\\{e\\}$.

For any $f\in N^{2}(e)$, as shown in Figure 3, there are six cases for the
induced subgraph $G[V(\\{e,f\\})]$. If $G[V(\\{e,f\\})]$ is the same as the
graph $H_{i}$, then we say that $f$ is a $2$-neighbor of Type $i$ of $e$,
where $i\in[1,6]$. And we denote by $T_{i}(e)$ the set of $2$-neighbors of
Type $i$ of $e$. It is clear that $N^{2}(e)=\cup_{i=1}^{6}T_{i}(e)$ and
$T_{i}(e)\cap T_{j}(e)=\emptyset$ for any two integers $i,j\in[1,6]$. In
addition, let $F(e)=N(e)\cup(\cup_{i=1}^{5}T_{i}(e))$. We have
$N^{2-}(e)=F(e)\cup T_{6}(e)$. For any $f\in N^{2}(e)$, $f\in F(e)$ if and
only if $e\in F(f)$, and $f\in T_{6}(e)$ if and only if $e\in T_{6}(f)$.

Figure 3: The six cases for the induced subgraph $G[V(\\{e,f\\})]$

According to the above definitions, we immediately observe the following.

###### Observation 1

Let $e=uv$ be an edge of $G$. If $C_{e}^{\Delta}=\emptyset$, then
$T_{1}(e)=T_{2}(e)=T_{3}(e)=\emptyset$.

We proceed to make another helpful observation.

###### Observation 2

Let $G$ be a graph with maximum degree $\Delta$. For any edge $e=uv$ of $G$,

$|F(e)|\leq\Delta^{2}-1-\frac{1}{2}|C_{e}^{\Delta}|-|T_{1}(e)|-\frac{1}{2}|T_{2}(e)|-\frac{1}{2}|T_{6}(e)|.$

Moreover, if equality holds, then each vertex in $N(u)\cup N(v)$ is of degree
$\Delta$.

Proof. Let $e=uv$ be an edge of $G$. On the one hand, according to the
partition of its $2$-neighbors, it is not difficult to see that

$\displaystyle\sum_{w\in N(u)\setminus\\{v\\}}(d(w)-1)+\sum_{w\in
N(v)\setminus\\{u\\}}(d(w)-1)$ $\displaystyle\geq$ $\displaystyle\
|C_{e}^{\Delta}|+4|T_{1}(e)|+3|T_{2}(e)|+2|T_{3}(e)|+2|T_{4}(e)|+2|T_{5}(e)|+|T_{6}(e)|$
$\displaystyle=$ $\displaystyle\
2|\cup_{i=1}^{5}T_{i}(e)|+|C_{e}^{\Delta}|+2|T_{1}(e)|+|T_{2}(e)|+|T_{6}(e)|.$

On the other hand, since $G$ is a graph with maximum degree $\Delta$, we have

$\displaystyle\sum\limits_{w\in
N(u)\setminus\\{v\\}}(d(w)-1)+\sum\limits_{w\in
N(v)\setminus\\{u\\}}(d(w)-1)\leq$ $\displaystyle\ 2(\Delta-1)^{2}.$ (1)

Combining the above two inequalities, it holds that

$\displaystyle|\cup_{i=1}^{5}T_{i}(e)|\leq$ $\displaystyle\
(\Delta-1)^{2}-\frac{1}{2}|C_{e}^{\Delta}|-|T_{1}(e)|-\frac{1}{2}|T_{2}(e)|-\frac{1}{2}|T_{6}(e)|.$

Notice that $F(e)=N(e)\cup(\cup_{i=1}^{5}T_{i}(e))$ and $|N(e)|\leq
2(\Delta-1)$, it is easy to check that

$\displaystyle|F(e)|\leq$ $\displaystyle\
\Delta^{2}-1-\frac{1}{2}|C_{e}^{\Delta}|-|T_{1}(e)|-\frac{1}{2}|T_{2}(e)|-\frac{1}{2}|T_{6}(e)|.$
(2)

It is clear that if (2) is an equality, then (1) must be an equality. This
implies that, for each $w\in N(u)\cup N(v)$, $d(w)=\Delta$. This completes the
proof of Observation 2.

Let $p$ be a positive integer. We use $\mathcal{G}_{p}$ to denote the family
of $p$-regular graphs $G$ with $2p$ vertices, in which there is an edge
$e=uv\in E(G)$ satisfying $N(u)\cup N(v)=V(G)$. It is clear that
$|E(G)|=p^{2}$ for each $G\in\mathcal{G}_{p}$ and $K_{p,p}\in\mathcal{G}_{p}$.
We are now ready to prove the following lemma.

###### Lemma 3.1

Let $G$ be a connected graph with maximum degree $\Delta$. Then there exists
an edge $e$ of $G$ such that $|F(e)|=\Delta^{2}-1$ if and only if
$G\in\mathcal{G}_{\Delta}$.

Proof. Let $e=uv$ be an edge of $G$ with $|F(e)|=\Delta^{2}-1$. By Observation
2, $C_{e}^{\Delta}=T_{1}(e)=T_{2}(e)=T_{6}(e)=\emptyset$ and $d(w)=\Delta$ for
each $w\in N(u)\cup N(v)$. At this time, we must have $V(G)=N(u)\cup N(v)$, as
otherwise since $G$ is connected, there exists a vertex $x\in
V(G)\setminus(N(u)\cup N(v))$ being adjacent to some vertex $w\in(N(u)\cup
N(v))\setminus\\{u,v\\}$. Then $xw$ is a $2$-neighbor of Type 6 of $e$ and so
obtain a contradiction. Therefore, we have $|V(G)|=2\Delta$ and thus
$G\in\mathcal{G}_{\Delta}$.

Let $G$ be a graph in $\mathcal{G}_{\Delta}$ and $e=uv$ be an edge of $G$
satisfying $N(u)\cup N(v)=V(G)$. It is obvious that $|E(G)|=\Delta^{2}$ and
$|N(e)|=2(\Delta-1)$. Notice that any edge $f\in E(G)\setminus N[e]$ is a
$2$-neighbor of $e$, $|N(e)|+|N^{2}(e)|=\Delta^{2}-1$. Since $N(u)\cup
N(v)=V(G)$, it holds that $T_{6}(e)=\emptyset$ and so
$|N(e)|+|N^{2}(e)|=|N(e)|+|\cup_{i=1}^{5}T_{i}(e)|=|F(e)|=\Delta^{2}-1$.
Hence, the lemma holds.

##  4 The proof of Theorem 2.3

It is sufficient to prove Theorem 2.3 for connected graphs. Let $G$ be a
connected graph with maximum degree $\Delta\geq 3$ that is not isomorphic to
$K_{\Delta,\Delta}$. The proof begins with the following lemma.

###### Lemma 4.1

If $G\in\mathcal{G}_{\Delta}$, distinct from $K_{\Delta,\Delta}$, then
$\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$ and
$\chi^{\prime}_{(0,1)}(G)\leq\Delta^{2}-1$.

Proof. Let $e$ be an edge of $G$ with $N(u)\cup N(v)=V(G)$. Because $G$
belongs to $\mathcal{G}_{\Delta}$ and is not isomorphic to
$K_{\Delta,\Delta}$, there exist two distinct vertices $u^{\prime}\in
N(u)\setminus\\{v\\}$ and $v^{\prime}\in N(v)\setminus\\{u\\}$ such that
$u^{\prime}v^{\prime}\notin E(G)$. This implies that $uu^{\prime}$ and
$vv^{\prime}$ do not lie on a common $4$-cycle. Notice that
$|E(G)|=\Delta^{2}$, a semistrong $(\Delta^{2}-1)$-edge-coloring of $G$ can be
easily obtained by coloring the two edges $uu^{\prime}$ and $vv^{\prime}$ with
the same color 1 and the remaining $\Delta^{2}-2$ edges with the other
$\Delta^{2}-2$ colors. This coloring is obviously a $(0,1)$-relaxed strong
edge coloring of $G$. Therefore, $\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$ and
$\chi^{\prime}_{(0,1)}(G)\leq\Delta^{2}-1$.

By the above lemma, we may assume that $G\notin\mathcal{G}_{\Delta}$ in the
rest of the proof. Recall that $K_{\Delta,\Delta}\in\mathcal{G}_{\Delta}$, $G$
is not isomorphic to $K_{\Delta,\Delta}$. Then it follows from Observation 2
and Lemma 3.1 that $|F(e)|\leq\Delta^{2}-2$ for each $e\in E(G)$. The greedy
algorithm, coloring the edges one by one in any order, will produce an edge
coloring with at most $\Delta^{2}-1$ colors, in which each edge $e$ receives a
color distinct from all colors of edges in $F(e)$. We call such a coloring
good.

Given a good coloring $\phi$ of $G$. For an edge $e$ of $G$, if it has at
least two $2$-neighbors with the same color as it under $\phi$, then we call
it a bad edge with respect to $\phi$. And for a $2$-neighbor $f$ of $e$ with
$\phi(e)=\phi(f)$, we call them a bad pair with respect to $\phi$. We denote
by $\kappa_{1}(\phi)$ (resp. $\kappa_{2}(\phi)$) the number of the bad edges
(resp. the bad pairs) with respect to $\phi$ in $G$. Similarly, we use
$\kappa_{1}(\phi,\alpha)$ (resp. $\kappa_{2}(\phi,\alpha)$) to denote the
number of the bad edges (resp. the bad pairs) being colored the color $\alpha$
with respect to $\phi$ in $G$. Based on the above definitions, we immediately
observe the following.

###### Observation 3

Let $\phi$ be a good coloring of a graph $G$. If no edge of $G$ is a bad edge
with respect to $\phi$, then $\phi$ is both a semistrong edge coloring and a
$(0,1)$-relaxed strong edge coloring.

Among all good colorings of $G$, we refer to a coloring with the fewest bad
edges as the $1$-optimal coloring of $G$. Moreover, if a $1$-optimal coloring
has the least number of bad pairs among all $1$-optimal colorings of $G$, then
we call it a $2$-optimal coloring of $G$.

Let $\phi$ be a $2$-optimal coloring of $G$. In the following, we devote to
prove that $\kappa_{1}(\phi)=0$ and so by Observation 3, $\phi$ is both a
semistrong edge coloring and a $(0,1)$-relaxed strong edge coloring of $G$.
Suppose to the contrary that $\kappa_{1}(\phi)>0$, i.e., there are bad edges
with respect to $\phi$ in $G$. For brevity, we will refer to the abbreviation
“the bad edges with respect to $\phi$” as “bad edges” and “the bad pairs with
respect to $\phi$” as “bad pairs”.

Recall that each bad edge $e$ in $G$ has at least two $2$-neighbors with the
same color as $e$. According to the definition of the good coloring of $G$, it
is obvious that for any bad edge $e$ in $G$, each $2$-neighbor of $e$ that is
colored with the same color as $e$ is of Type $6$. We continue by showing
several properties of bad edges in $G$.

###### Claim 1

Let $e$ be a bad edge in $G$. For any color
$\alpha\in[1,\Delta^{2}-1]\setminus\phi(F(e))$, there are at least two edges
in $T_{6}(e)$ being colored $\alpha$ in $\phi$. This implies that
$|\phi(N^{2-}(e))|=\Delta^{2}-1$.

Proof. Let $e$ be a bad edge in $G$ with $\phi(e)=\alpha_{0}$. It is clear
that $\alpha_{0}$ appears on at least two edges in $T_{6}(e)$. If there exists
a color $\alpha\in[1,\Delta^{2}-1]\setminus\phi(F(e))$ such that at most one
edge in $T_{6}(e)$ being colored $\alpha$ in $\phi$, then we recolor the edge
$e$ with the color $\alpha$ to obtain a new coloring $\psi$ of $G$. It is
obvious that $\psi$ is a good coloring of $G$. And it is easy to see that
$\kappa_{1}(\psi,\alpha_{0})\leq\kappa_{1}(\phi,\alpha_{0})-1$,
$\kappa_{1}(\psi,\alpha)\leq\kappa_{1}(\phi,\alpha)+1$ and
$\kappa_{1}(\psi,\beta)=\kappa_{1}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{0},\alpha\\}$. It follows that
$\kappa_{1}(\psi)\leq\kappa_{1}(\phi)$. Moreover,
$\kappa_{2}(\psi,\alpha_{0})\leq\kappa_{2}(\phi,\alpha_{0})-2$,
$\kappa_{2}(\psi,\alpha)\leq\kappa_{2}(\phi,\alpha)+1$ and
$\kappa_{2}(\psi,\beta)=\kappa_{2}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{0},\alpha\\}$. Thus we have
$\kappa_{2}(\psi)<\kappa_{2}(\phi)$, contradicting the $2$-optimality of
$\phi$. The claim is proved.

###### Claim 2

Each bad edge $e$ in $G$ has the following five properties:

$(1)$ $\phi(F(e))\cap\phi(T_{6}(e))=\emptyset$;

$(2)$ $|\phi(T_{6}(e))|=\frac{1}{2}|T_{6}(e)|$, i.e., the colors on the edges
in $T_{6}(e)$ appear in pairs;

$(3)$ $|\phi(F(e))|=|F(e)|=\Delta^{2}-1-\frac{1}{2}|T_{6}(e)|$, i.e., all
edges in $F(e)$ receive different colors;

$(4)$ $C_{e}^{\Delta}=\emptyset$ $($and so
$T_{1}(e)=T_{2}(e)=T_{3}(e)=\emptyset$ and $N^{2}(e)=T_{4}(e)\cup T_{5}(e)\cup
T_{6}(e)$$)$;

$(5)$ for any $w\in N(u)\cup N(v)$, $d(w)=\Delta$.

Proof. Let $e$ be a bad edge in $G$ with $\phi(e)=\alpha_{0}$. By Claim 1,
each color in $[1,\Delta^{2}-1]\setminus\phi(F(e))$ appears on at least two
edges in $T_{6}(e)$. This implies that
$|\phi(T_{6}(e))\setminus\phi(F(e))|\leq\frac{1}{2}|T_{6}(e)|$. According to
Observation 2, we have

$\displaystyle|\phi(N^{2-}(e))|=$
$\displaystyle|\phi(F(e))|+|\phi(T_{6}(e))\setminus\phi(F(e))|$
$\displaystyle\leq$ $\displaystyle\ |F(e)|+\frac{1}{2}|T_{6}(e)|$
$\displaystyle\leq$ $\displaystyle\
\Delta^{2}-1-\frac{1}{2}|C_{e}^{\Delta}|-|T_{1}(e)|-\frac{1}{2}|T_{2}(e)|.$

Recall that $|\phi(N^{2-}(e))|=\Delta^{2}-1$ (see Claim 1), we must have

$\displaystyle|\phi(T_{6}(e))\setminus\phi(F(e))|=$ $\displaystyle\
\frac{1}{2}|T_{6}(e)|,$ (3) $\displaystyle|\phi(F(e))|=$ $\displaystyle\
|F(e)|,$ (4) $\displaystyle C_{e}^{\Delta}=$ $\displaystyle\ \emptyset,$ (5)
$\displaystyle|F(e)|=$ $\displaystyle\ \Delta^{2}-1-\frac{1}{2}|T_{6}(e)|.$
(6)

Then the first four properties are easy to see due to the above equations. And
Property (5) follows directly from Equation (6) and Observation 2. Thus the
claim holds.

According to Claim 2(2), we immediately have the following observation.

###### Observation 4

Each bad edge $e$ in $G$ has exactly two $2$-neighbors of Type $6$ with the
same color as $e$.

###### Claim 3

Let $e$ be a bad edge in $G$. For any $1$-neighbor $f$ of $e$, if there exists
some color $\alpha\in[1,\Delta^{2}-1]\setminus\phi(F(f)\cup\\{f\\})$, then
there are at least two edges in $T_{6}(f)$ being colored $\alpha$ in $\phi$.
This implies that $|\phi(N^{2-}[f])|=\Delta^{2}-1$ and
$|\phi(N^{2-}(f))|\geq\Delta^{2}-2$.

Proof. Let $e$ be a bad edge $e$ in $G$ and $f$ be a $1$-neighbor of $e$ with
$[1,\Delta^{2}-1]\setminus\phi(F(f)\cup\\{f\\})\neq\emptyset$. For
convenience, let $\alpha_{0}=\phi(e)$ and $\alpha_{1}=\phi(f)$. We prove by
contradiction. If some color
$\alpha\in[1,\Delta^{2}-1]\setminus\phi(F(f)\cup\\{f\\})$ appears at most once
on edges in $T_{6}(f)$. Then we can obtain a new coloring $\psi$ by recoloring
$f$ with the color $\alpha$ and $e$ with the color $\alpha_{1}$. Since $f\in
N(e)$, by Claim 2, $\alpha_{1}\notin\phi(N^{2-}(e)\setminus\\{f\\})$. Thus it
is easy to see that $\psi$ is a good coloring of $G$. Moreover, we have
$\kappa_{1}(\psi,\alpha_{0})\leq\kappa_{1}(\phi,\alpha_{0})-1$,
$\kappa_{1}(\psi,\alpha_{1})\leq\kappa_{1}(\phi,\alpha_{1})$,
$\kappa_{1}(\psi,\alpha)\leq\kappa_{1}(\phi,\alpha)+1$ and
$\kappa_{1}(\psi,\beta)=\kappa_{1}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{0},\alpha_{1},\alpha\\}$. It
follows that $\kappa_{1}(\psi)\leq\kappa_{1}(\phi)$. Furthermore, we have
$\kappa_{2}(\psi,\alpha_{0})=\kappa_{2}(\phi,\alpha_{0})-2$,
$\kappa_{2}(\psi,\alpha_{1})\leq\kappa_{2}(\phi,\alpha_{1})$,
$\kappa_{2}(\psi,\alpha)\leq\kappa_{2}(\phi,\alpha)+1$ and
$\kappa_{2}(\psi,\beta)=\kappa_{2}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{0},\alpha_{1},\alpha\\}$.
Therefore, $\kappa_{2}(\psi)<\kappa_{2}(\phi)$. This contradicts the
$2$-optimality of $\phi$ and so the claim follows.

###### Claim 4

Given a bad edge $e=uv$ in $G$. Let $e_{1}$ and $e_{2}$ be two $2$-neighbors
of $e$ with $\phi(e_{1})=\phi(e_{2})=\phi(e)$. Then we have
$|\\{e_{1},e_{2}\\}\cap N_{u}^{2}(e)|=1$ and $|\\{e_{1},e_{2}\\}\cap
N_{v}^{2}(e)|=1$.

Proof. If not, by symmetry, we may assume that $\\{e_{1},e_{2}\\}\subseteq
N_{u}^{2}(e)$. Denote by $f$ the edge in $N(e)$ being adjacent to $e_{1}$. It
is clear that $e,e_{1}\in N(f)$, $e_{2}\in N^{2}(f)$ and $e_{2}\notin
C^{\Delta}_{f}$. Since $\phi(e)=\phi(e_{1})=\phi(e_{2})$, by Claim 3 and
Observation 2, we have

$\displaystyle|\phi(N^{2-}(f))|\leq$ $\displaystyle\
|F(f)|-1+\frac{1}{2}(|T_{6}(f)|-1)$ $\displaystyle\leq$ $\displaystyle\
\Delta^{2}-\frac{5}{2}-\frac{1}{2}|C_{f}^{\Delta}|-|T_{1}(f)|-\frac{1}{2}|T_{2}(f)|.$

As $|\phi(N^{2-}(f))|$ is an integer, $|\phi(N^{2-}(f))|\leq\Delta^{2}-3$,
contradicting the fact that $|\phi(N^{2-}(f))|\geq\Delta^{2}-2$ (refer to
Claim 3). This finishes the proof of the claim.

###### Claim 5

For each bad edge $e$ in $G$, $T_{5}(e)=\emptyset$ and $N^{2}(e)=T_{4}(e)\cup
T_{6}(e)$. This implies that, for any $f\in N(e)$, $C_{f}^{\Delta}=\emptyset$
$($and so $T_{1}(f)=T_{2}(f)=T_{3}(f)=\emptyset$ and $N^{2}(f)=T_{4}(f)\cup
T_{5}(f)\cup T_{6}(f)$$)$.

Proof. Let $e$ be a bad edge. Suppose that $T_{5}(e)\neq\emptyset$. Without
loss of generality, let $g$ be an edge in $T_{5}(e)\cap N_{u}^{2}(e)$ and $f$
be an edge in $N_{u}(e)$ being adjacent to $g$. It follows that
$|C_{f}^{\Delta}|\geq 2$. By Claim 4, there exists one edge $e_{1}$ in
$N_{u}^{2}(e)$ with $\phi(e_{1})=\phi(e)$. Notice that $e\in N(f)$ and
$e_{1}\in N^{2-}(f)$, according to Claim 3 and Observation 2, we immediately
have

$\displaystyle|\phi(N^{2-}(f))|\leq$ $\displaystyle\
|F(f)|+\frac{1}{2}(|T_{6}(f)|-1)$ $\displaystyle\leq$ $\displaystyle\
\Delta^{2}-1-\frac{1}{2}|C_{f}^{\Delta}|-|T_{1}(f)|-\frac{1}{2}|T_{2}(f)|-\frac{1}{2}$
$\displaystyle\leq$ $\displaystyle\ \Delta^{2}-1-\frac{1}{2}\times
2-|T_{1}(f)|-\frac{1}{2}|T_{2}(f)|-\frac{1}{2}$ $\displaystyle=$
$\displaystyle\ \Delta^{2}-\frac{5}{2}-|T_{1}(f)|-\frac{1}{2}|T_{2}(f)|.$

Since $|\phi(N^{2-}(f))|$ is an integer, $|\phi(N^{2-}(f))|\leq\Delta^{2}-3$.
This is a contradiction to Claim 3. Thus $T_{5}(e)=\emptyset$. By Claim 2(4),
$N^{2}(e)=T_{4}(e)\cup T_{6}(e)$. The claim is proved.

###### Claim 6

For each bad edge $e=uv$ in $G$, $|\phi(N(e)\cup N_{u}^{2}(e))|=|N(e)\cup
N_{u}^{2}(e)|=\Delta^{2}-1$ and $|\phi(N(e)\cup N_{v}^{2}(e))|=|N(e)\cup
N_{v}^{2}(e)|=\Delta^{2}-1$ $($refer to Figure 4, all the bold edges receive
different colors$)$.

Figure 4: The illustration of Claim 6

Proof. Let $e=uv$ be a bad edge with the color $\alpha_{0}$. Since any vertex
in $N(u)\cup N(v)$ is of degree $\Delta$ (see Claim 2(5)), $|N(e)\cup
N_{u}^{2}(e)|=|N(e)\cup N_{v}^{2}(e)|=\Delta^{2}-1$. In the following, we
prove that $|\phi(N(e)\cup N_{u}^{2}(e))|=|\phi(N(e)\cup
N_{v}^{2}(e))|=\Delta^{2}-1$. Suppose that $|\phi(N(e)\cup
N_{u}^{2}(e))|<\Delta^{2}-1$. Let
$\alpha\in[1,\Delta^{2}-1]\setminus\phi(N(e)\cup N_{u}^{2}(e))$.

According to Claim 4, we assume that $e_{1}\in N_{u}^{2}(e)\cap T_{6}(e)$ and
$e_{2}\in N_{v}^{2}(e)\cap T_{6}(e)$ are the two distinct $2$-neighbors of $e$
being colored $\alpha_{0}$. It is obvious that $\alpha\neq\alpha_{0}$. By
Claim 5, $N^{2-}(e)=N(e)\cup T_{4}(e)\cup T_{6}(e)$. Notice that
$T_{4}(e)=N_{u}^{2}(e)\cap N_{v}^{2}(e)$, the color $\alpha$ appears on
exactly two edges in $N_{v}^{2}(e)\cap T_{6}(e)$ as
$|\phi(N^{2-}(e))|=\Delta^{2}-1$ (see Claim 1) and the colors on the edges in
$T_{6}(e)$ appear in pairs (see Claim 2(2)). It follows that there are exactly
two edges $f_{1}$ and $f_{2}$ in $N_{u}^{2}(e)\cap T_{6}(e)$ such that
$\phi(f_{1})=\phi(f_{2})\neq\alpha$. Denote by $h_{1}$ and $h_{2}$ the edges
in $N(e)$ being adjacent to $f_{1}$ and $f_{2}$, respectively. It is clear
that $h_{1}\neq h_{2}$. And we may assume that $e_{1}\notin N(h_{1})$ and so
$e_{1}\in N^{2}(h_{1})$. According to Claim 5, $C_{h_{1}}^{\Delta}=\emptyset$
and $N^{2}(h_{1})=T_{4}(h_{1})\cup T_{5}(h_{1})\cup T_{6}(h_{1})$.

We first prove that $e_{1}\in T_{6}(h_{1})$. If $e_{1}\in T_{5}(h_{1})$, then
as $C_{h_{1}}^{\Delta}=\emptyset$, we must have $e_{1}\in T_{5}(e)$, which is
a contradiction since $e_{1}\in T_{6}(e)$. And if $e_{1}\in T_{4}(h_{1})$,
notice that $e,e_{1},f_{1}\in F(h_{1})$, $f_{2}\in N^{2}(h_{1})$,
$\phi(e)=\phi(e_{1})$ and $\phi(f_{1})=\phi(f_{2})$, by Claim 3 and
Observation 2, we have

$\displaystyle|\phi(N^{2-}(h_{1}))|\leq$ $\displaystyle\
|F(h_{1})|-1+\frac{1}{2}(|T_{6}(h_{1})|-1)$ $\displaystyle\leq$
$\displaystyle\
\Delta^{2}-\frac{5}{2}-\frac{1}{2}|C_{h_{1}}^{\Delta}|-|T_{1}(h_{1})|-\frac{1}{2}|T_{2}(h_{1})|.$

Since $|\phi(N^{2-}(h_{1}))|$ is an integer,
$|\phi(N^{2-}(h_{1}))|\leq\Delta^{2}-3$, contradicting the conclusion in Claim
3 that $|\phi(N^{2-}(h_{1}))|\geq\Delta^{2}-2$. Therefore, $e_{1}\in
T_{6}(h_{1})$.

Next we prove that there is no edge in $N^{2-}(h_{1})\setminus\\{e,e_{1}\\}$
being colored $\alpha_{0}$. If not, let $e^{*}$ be an edge in
$N^{2-}(h_{1})\setminus\\{e,e_{1}\\}$ that is colored with $\alpha_{0}$.
Recall that no edge in $N^{2-}(e)$ is colored $\alpha_{0}$ except $e_{1}$ and
$e_{2}$, we must have $e^{*}\notin N(h_{1})\cup T_{4}(h_{1})$ since any edge
in $(N(h_{1})\cup T_{4}(h_{1}))\setminus\\{e\\}$ is also in $N^{2-}_{u}(e)$.
As $N^{2-}(h_{1})=N(h_{1})\cup T_{4}(h_{1})\cup T_{5}(h_{1})\cup
T_{6}(h_{1})$, $e^{*}\in T_{5}(h_{1})\cup T_{6}(h_{1})$. If $e^{*}\in
T_{5}(h_{1})$, notice that $e,e^{*},f_{1}\in F(h_{1})$, $f_{2}\in
N^{2}(h_{1})$, $e_{1}\in T_{6}(h_{1})$, $\phi(e)=\phi(e^{*})=\phi(e_{1})$ and
$\phi(f_{1})=\phi(f_{2})$, again by Claim 3 and Observation 2, we have

$\displaystyle|\phi(N^{2-}(h_{1}))|\leq$ $\displaystyle\
|F(h_{1})|-1+\frac{1}{2}(|T_{6}(h_{1})|-2)$ $\displaystyle\leq$
$\displaystyle\
\Delta^{2}-3-\frac{1}{2}|C_{h_{1}}^{\Delta}|-|T_{1}(h_{1})|-\frac{1}{2}|T_{2}(h_{1})|,$

this is a contradiction to Claim 3. And if $e^{*}\in T_{6}(h_{1})$, notice
that $e,f_{1}\in N(h_{1})$, $f_{2}\in N^{2}(h_{1})$, $e_{1},e^{*}\in
T_{6}(h_{1})$, $\phi(e)=\phi(e_{1})=\phi(e^{*})$ and
$\phi(f_{1})=\phi(f_{2})$,

$\displaystyle|\phi(N^{2-}(h_{1}))|\leq$ $\displaystyle\
|F(h_{1})|+\frac{1}{2}(|T_{6}(h_{1})|-3)$ $\displaystyle\leq$ $\displaystyle\
\Delta^{2}-\frac{5}{2}-\frac{1}{2}|C_{h_{1}}^{\Delta}|-|T_{1}(h_{1})|-\frac{1}{2}|T_{2}(h_{1})|.$

Again we have $|\phi(N^{2-}(h_{1}))|\leq\Delta^{2}-3$, a contradiction to
Claim 3.

Now we can exchange the colors of $e$ and $h_{1}$ in $\phi$ to get a new
coloring $\psi$ of $G$. Since $h_{1}\in N(e)$, by Claim 2,
$\phi(h_{1})\notin\phi(N^{2-}(e)\setminus\\{h_{1}\\})$ and thus
$\psi(e)\notin\psi(N^{2-}(e))$. Because $e_{1}$ is the only edge in
$N^{2-}(h_{1})$ that is colored with $\alpha_{0}$ in $\psi$ and $e_{1}\in
T_{6}(h_{1})$, $\psi(h_{1})\notin\psi(F(h_{1}))$ and $h_{1}$ is not a bad edge
with respect to $\psi$. Therefore, $\psi$ is a good coloring of $G$. And it is
easy to check that
$\kappa_{1}(\psi,\alpha_{0})\leq\kappa_{1}(\phi,\alpha_{0})-1$,
$\kappa_{1}(\psi,\phi(h_{1}))\leq\kappa_{1}(\phi,\phi(h_{1}))$ and
$\kappa_{1}(\psi,\beta)=\kappa_{1}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{0},\phi(h_{1})\\}$. Therefore,
$\kappa_{1}(\psi)<\kappa_{1}(\phi)$, which contradicts the $1$-optimality of
$\phi$. Consequently, $|\phi(N(e)\cup N_{u}^{2}(e))|=\Delta^{2}-1$. By
symmetry, $|\phi(N(e)\cup N_{v}^{2}(e))|=\Delta^{2}-1$. The claim is proved.

Based on Claims 2(2) and 6, we immediately observe the following.

###### Observation 5

For each bad edge $e=uv$ in $G$, $|T_{6}(e)|$ is even and $|\phi(T_{6}(e)\cap
N^{2}_{u}(e))|=|T_{6}(e)\cap N^{2}_{u}(e)|=|T_{6}(e)\cap
N^{2}_{v}(e)|=|\phi(T_{6}(e)\cap N^{2}_{v}(e))|$.

Let $k\geq 2$ be an integer. Suppose $P_{k}=v_{0}v_{1}v_{2}\ldots v_{k}$ is an
induced path in $G$ with $v_{0}v_{1}$ being a bad edge. In the following two
claims, we consider the properties of this path. For each $i\in[1,k]$, denote
by $e_{i}$ the edge $v_{i-1}v_{i}$ and let

$\begin{array}[]{rl}M_{e_{i}}=\begin{cases}N(e_{1})\cup
N_{v_{1}}^{2}(e_{1}),&i=1,\\\ (N[e_{i}]\setminus\\{e_{i-1}\\})\cup
N_{v_{i}}^{2}(e_{i}),&2\leq i\leq k.\end{cases}\end{array}$

As shown in Figure 5, the edge set $M_{e_{i}}$ ($2\leq i\leq k$) is indicated
by bold edges. Notice that $e_{1}\notin M_{e_{1}}$ and $e_{i}\in M_{e_{i}}$
for each $2\leq i\leq k$.

Figure 5: The illustration of $M_{e_{i}}\ (2\leq i\leq k)$

###### Claim 7

Let $k\geq 2$ be an integer. Suppose $P_{k}=v_{0}v_{1}v_{2}\ldots v_{k}$ is an
induced path in $G$ with $v_{0}v_{1}$ being a bad edge. Then, for each $1\leq
i\leq k$, $|\phi(M_{e_{i}})|=|M_{e_{i}}|=\Delta^{2}-1$.

Proof. Because $e_{1}$ is a bad edge, it follows from Claim 6 that this claim
holds for $i=1$. For any integer $2\leq i\leq k$, it holds that
$|\phi(M_{e_{i}})|\leq|M_{e_{i}}|=|N_{v_{i-1}}[e_{i}]\setminus\\{e_{i-1}\\}|+|N_{v_{i}}^{2-}(e_{i})|\leq(\Delta-1)+\Delta(\Delta-1)=\Delta^{2}-1$.
Therefore, we just need to prove $|\phi(M_{e_{i}})|=\Delta^{2}-1$ for each
$2\leq i\leq k$. For convenience, let $\alpha_{i}=\phi(e_{i})$ for each
$i\in[1,k]$. We proceed by induction on $k$.

For $k=2$, if $|\phi(M_{e_{2}})|<\Delta^{2}-1$, then we can recolor $e_{2}$
with some color $\alpha\in[1,\Delta^{2}-1]\setminus\phi(M_{e_{2}})$ and
$e_{1}$ with the color $\alpha_{2}$. This yields a new coloring of $G$ called
$\psi$. It is clear that $\alpha_{2}\neq\alpha$.

Since $e_{1}$ is a bad edge with respect to $\phi$ and $e_{2}\in N(e_{1})$, by
Claim 6, $\alpha_{2}\notin\phi(N^{2-}(e_{1})\setminus\\{{e_{2}}\\})$ and so
$\alpha_{2}\notin\psi(N^{2-}(e_{1}))$, that is
$\psi(e_{1})\notin\psi(F(e_{1}))$. Recall that
$|\phi(M_{e_{1}})|=|M_{e_{1}}|=\Delta^{2}-1$, there is exactly one edge $f$ in
$M_{e_{1}}$ being colored $\alpha$ under $\phi$. Because
$\alpha\notin\phi(M_{e_{2}})$, $f\in M_{e_{1}}\setminus M_{e_{2}}$ and so $f$
is a $2$-neighbor of $e_{2}$. Notice that $T_{4}(e_{2})\subseteq M_{e_{2}}$,
$f\notin T_{4}(e_{2})$. Notice also that $C_{e_{1}}^{\Delta}=\emptyset$ (see
Claim 2(4)) and $T_{5}(e_{1})=\emptyset$ (see Claim 5), we must have $f\in
T_{6}(e_{2})$ and thus $\psi(e_{2})\notin\psi(F(e_{2}))$. Therefore, $\psi$ is
a good coloring of $G$.

It is easy to see that
$\kappa_{1}(\psi,\alpha_{1})\leq\kappa_{1}(\phi,\alpha_{1})-1$,
$\kappa_{1}(\psi,\alpha_{2})\leq\kappa_{1}(\phi,\alpha_{2})$,
$\kappa_{1}(\psi,\alpha)\leq\kappa_{1}(\phi,\alpha)+1$ and
$\kappa_{1}(\psi,\beta)=\kappa_{1}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{1},\alpha_{2},\alpha\\}$. It
follows that $\kappa_{1}(\psi)\leq\kappa_{1}(\phi)$. Moreover, it is clear
that $\kappa_{2}(\psi,\alpha_{1})=\kappa_{2}(\phi,\alpha_{1})-2$,
$\kappa_{2}(\psi,\alpha_{2})\leq\kappa_{2}(\phi,\alpha_{2})$,
$\kappa_{2}(\psi,\alpha)\leq\kappa_{2}(\phi,\alpha)+1$ and
$\kappa_{2}(\psi,\beta)=\kappa_{2}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{1},\alpha_{2},\alpha\\}$. This
implies that $\kappa_{2}(\psi)<\kappa_{2}(\phi)$, which is a contradiction to
the $2$-optimality of $\phi$. Hence,
$|\phi(M_{e_{2}})|=|M_{e_{2}}|=\Delta^{2}-1$.

Next we consider the case that $k\geq 3$. Assume that
$|\phi(M_{e_{i}})|=|M_{e_{i}}|=\Delta^{2}-1$ holds for any integer $1\leq
i\leq k-1$. In the following, we prove that $|\phi(M_{e_{k}})|=\Delta^{2}-1$.
If not, let $\alpha\in[1,\Delta^{2}-1]\setminus\phi(M_{e_{k}})$. It is obvious
that $\alpha\neq\alpha_{k}$. But it is possible that $\alpha=\alpha_{k-1}$.
Then, we recolor $e_{i}$ with the color $\alpha_{i+1}$ for each $i\in[1,k-1]$
and $e_{k}$ with the color $\alpha$. This results in a new coloring of $G$
called $\psi$, in which $\psi(e_{k})=\alpha$ and $\psi(e_{i})=\alpha_{i+1}$
for each $i\in[1,k-1]$.

Because $P_{k}=v_{0}v_{1}v_{2}\ldots v_{k}$ is an induced path in $G$ with
$e_{1}$ being a bad edge and $|\phi(M_{e_{i}})|=|M_{e_{i}}|=\Delta^{2}-1$ for
each $1\leq i\leq k-1$, we immediately observe the following.

###### Observation 6

For each $1\leq i\leq k-2$, $e_{i+2}\in T_{6}(e_{i})$ and $e_{i}\in
T_{6}(e_{i+2})$. Moreover, if $k\geq 4$, then $\alpha_{i}\neq\alpha_{i+2}$ for
each $2\leq i\leq k-2$.

Recall that $|M_{e_{i}}|=\Delta^{2}-1$ for each $1\leq i\leq k-1$, the
following observation follows directly.

###### Observation 7

For each $1\leq i\leq k-1$, $C_{e_{i}}^{\Delta}=\emptyset$ and
$T_{5}(e_{i})=\emptyset$.

Before proceeding with the proof, we make two other useful observations.

###### Observation 8

$e_{k}$ has exactly one $2$-neighbor $f$ being colored $\alpha$ under $\psi$
and $f\in T_{6}(e_{k})$.

Proof. Since $|\phi(M_{e_{k-1}})|=|M_{e_{k-1}}|=\Delta^{2}-1$ and
$\alpha\notin\phi(M_{e_{k}})$, there is exactly one edge in
$M_{e_{k-1}}\setminus M_{e_{k}}$ being colored $\alpha$ under $\phi$. It
follows that exactly one edge $f$ in $(M_{e_{k-1}}\setminus
M_{e_{k}})\cup\\{e_{k-2}\\}$ is colored $\alpha$ under $\psi$. Now, if
$f=e_{k-2}$, then it is clear that $f\in T_{6}(e_{k})$ due to Observation 6.
And if $f\in M_{e_{k-1}}\setminus M_{e_{k}}$, then since
$C_{e_{k-1}}^{\Delta}=\emptyset$ and $T_{5}(e_{k-1})=\emptyset$ (see
Observation 7), it is easy to check that $f\in T_{6}(e_{k})$.

###### Observation 9

$\alpha_{k-1}\notin\psi(N^{2-}(e_{k-2})\setminus\\{e_{k}\\})$, and
$\alpha_{i}\notin\psi(N^{2-}(e_{i-1}))$ for $2\leq i\leq k$ and $i\neq k-1$.

Proof. We first prove that $\alpha_{k}\notin\psi(N^{2-}(e_{k-1}))$. Since
$|\phi(M_{e_{k-2}})|=|M_{e_{k-2}}|=\Delta^{2}-1$ and
$|\phi(M_{e_{k-1}})|=|M_{e_{k-1}}|=\Delta^{2}-1$,
$\alpha_{k}\notin\phi(M_{e_{k-2}}\setminus\\{e_{k}\\})$ and
$\alpha_{k}\notin\phi(M_{e_{k-1}}\setminus\\{e_{k}\\})$, respectively. It
follows that $\alpha_{k}\notin\psi(N^{2-}(e_{k-1}))$ as
$\alpha_{k}\neq\alpha$.

Then we prove that for each $2\leq i\leq k-1$,
$\alpha_{i}\notin\psi(N^{2-}(e_{i-1})\setminus\\{e_{i+1}\\})$. Recall that
$e_{1}$ is a bad edge with respect to $\phi$ and $e_{2}\in N(e_{1})$, by Claim
6, $\alpha_{2}\notin\phi(N^{2-}(e_{1})\setminus\\{{e_{2}}\\})$ and thus
$\alpha_{2}\notin\psi(N^{2-}(e_{1})\setminus\\{e_{3}\\})$ (notice that
possibly $\alpha_{2}=\alpha$). Now, if $k=3$, the proof is complete. While if
$k\geq 4$, for each $3\leq i\leq k-1$, because
$|\phi(M_{e_{i-2}})|=|M_{e_{i-2}}|=\Delta^{2}-1$ and
$|\phi(M_{e_{i-1}})|=|M_{e_{i-1}}|=\Delta^{2}-1$,
$\alpha_{i}=\phi(e_{i})\notin\phi(M_{e_{i-2}}\setminus\\{e_{i}\\})$ and
$\alpha_{i}=\phi(e_{i})\notin\phi(M_{e_{i-1}}\setminus\\{e_{i}\\})$,
respectively. It follows that
$\alpha_{i}\notin\psi(N^{2-}(e_{i-1})\setminus\\{e_{i+1}\\})$ for each $2\leq
i\leq k-1$.

Finally, due to Observation 6, for each $2\leq i\leq k-2$,
$\alpha_{i}\neq\alpha_{i+2}=\psi(e_{i+1})$. This, together with
$\alpha_{i}\notin\psi(N^{2-}(e_{i-1})\setminus\\{e_{i+1}\\})$, implies that
$\alpha_{i}\notin\psi(N^{2-}(e_{i-1}))$ for each $2\leq i\leq k-2$. Therefore,
Observation 9 is proved.

In light of Observations 8 and 9, it is easy to see that
$\psi(e_{i})\notin\psi(F(e_{i}))$ for each $1\leq i\leq k$. Therefore, $\psi$
is a good coloring of $G$. Moreover, these two observations also imply that
$\kappa_{1}(\psi,\alpha_{i})\leq\kappa_{1}(\phi,\alpha_{i})$ for each $2\leq
i\leq k$ and $\kappa_{1}(\psi,\alpha)\leq\kappa_{1}(\phi,\alpha)+1$. Notice
that $\kappa_{1}(\psi,\alpha_{1})\leq\kappa_{1}(\phi,\alpha_{1})-1$ and
$\kappa_{1}(\psi,\beta)=\kappa_{1}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{k},\alpha\\}$,
we must have $\kappa_{1}(\psi)\leq\kappa_{1}(\phi)$. And it is easy to check
that $\kappa_{2}(\psi,\alpha_{1})\leq\kappa_{2}(\phi,\alpha_{1})-2$,
$\kappa_{2}(\psi,\alpha)\leq\kappa_{2}(\phi,\alpha)+1$ and
$\kappa_{2}(\psi,\beta)\leq\kappa_{2}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{1},\alpha\\}$. Therefore, it
holds that $\kappa_{2}(\psi)<\kappa_{2}(\phi)$, a contradiction to the
$2$-optimality of $\phi$. Hence, $|\phi(M_{e_{k}})|=|M_{e_{k}}|=\Delta^{2}-1$.
This proves the claim.

###### Claim 8

Let $k\geq 2$ be an integer. Suppose $P_{k}=v_{0}v_{1}v_{2}\ldots v_{k}$ is an
induced path in $G$ with $v_{0}v_{1}$ being a bad edge. Then we have the
following three conclusions.

$(1)$ For each $1\leq i\leq k$, $C_{e_{i}}^{\Delta}=\emptyset$,
$T_{5}(e_{i})=\emptyset$ and $N^{2}(e_{i})=T_{4}(e_{i})\cup T_{6}(e_{i})$;

$(2)$ For each $2\leq i\leq k$ and $i\neq 3$,
$\phi(e_{i})\notin\phi(N^{2-}(e_{i}))$; and while if $k\geq 3$, then
$\phi(e_{3})\notin\phi(N^{2-}(e_{3})\setminus\\{e_{1}\\})$;

$(3)$ If $k\geq 3$, then for each $3\leq i\leq k$, there is exactly one edge
$h_{i}\in N^{2}_{v_{i}}(e_{i})$ such that $\phi(h_{i})=\phi(e_{i-1})$;
moreover, $h_{i}\in T_{6}(e_{i})$.

Proof. The first conclusion holds for $i=1$ due to Claim 5. Because
$P_{k}=v_{0}v_{1}v_{2}\ldots v_{k}$ is an induced path in $G$ with $e_{1}$
being a bad edge, by Claim 7, $|\phi(M_{e_{i}})|=|M_{e_{i}}|=\Delta^{2}-1$ for
each $1\leq i\leq k$. Thus for each $2\leq i\leq k$, we must have
$C_{e_{i}}^{\Delta}=\emptyset$ and $T_{5}(e_{i})=\emptyset$ as otherwise there
is a contradiction to the fact that $|M_{e_{i-1}}|=|M_{e_{i}}|=\Delta^{2}-1$.
Therefore, conclusion (1) is correct.

Then we prove conclusion (2). Because
$|\phi(M_{e_{1}})|=|M_{e_{1}}|=\Delta^{2}-1$,
$|\phi(M_{e_{2}})|=|M_{e_{2}}|=\Delta^{2}-1$ and $e_{2}\in M_{e_{1}}\cap
M_{e_{2}}$, $\phi(e_{2})\notin\phi(N^{2-}(e_{2})\setminus\\{e_{1}\\})$. Notice
that $e_{2}\in N(e_{1})$, we have $\phi(e_{2})\neq\phi(e_{1})$ and thus
$\phi(e_{2})\notin\phi(N^{2-}(e_{2}))$. While if $k\geq 3$, for each $3\leq
i\leq k$, since $|\phi(M_{e_{i-1}})|=|M_{e_{i-1}}|=\Delta^{2}-1$,
$|\phi(M_{e_{i}})|=|M_{e_{i}}|=\Delta^{2}-1$ and $e_{i}\in M_{e_{i-1}}\cap
M_{e_{i}}$, it holds that
$\phi(e_{i})\notin\phi(N^{2-}(e_{i})\setminus\\{e_{i-2}\\})$. When $k\geq 4$,
for each $4\leq i\leq k$, since $e_{i-2},e_{i}\in M_{e_{i-2}}$ and
$|\phi(M_{e_{i-2}})|=|M_{e_{i-2}}|=\Delta^{2}-1$, we have
$\phi(e_{i})\neq\phi(e_{i-2})$ and thus
$\phi(e_{i})\notin\phi(N^{2-}(e_{i}))$.

Finally, we prove that conclusion (3) is also correct. For each $3\leq i\leq
k$, since $|\phi(M_{e_{i}})|=|M_{e_{i}}|=\Delta^{2}-1$ and $e_{i-1}\notin
M_{e_{i}}$, there is exactly one edge $h_{i}$ in $M_{e_{i}}$ such that
$\phi(h_{i})=\phi(e_{i-1})$. Because
$|\phi(M_{e_{i-1}})|=|M_{e_{i-1}}|=\Delta^{2}-1$ and $e_{i-1}\in M_{e_{i-1}}$,
$\phi(e_{i-1})\notin\phi(M_{e_{i-1}}\setminus\\{e_{i-1}\\})$. Recall that
$M_{e_{i}}=(N[e_{i}]\setminus\\{e_{i-1}\\})\cup N^{2}_{v_{i}}(e_{2})$, we must
have $h_{i}\in N^{2}_{v_{i}}(e_{2})$ as
$N[e_{i}]\setminus\\{e_{i-1}\\}\subseteq M_{e_{i-1}}\setminus\\{e_{i-1}\\}$.
Due to conclusion (1), $N^{2}(e_{i})=T_{4}(e_{i})\cup T_{6}(e_{i})$. If
$h_{i}\in T_{4}(e_{i})$, then $h_{i}\in M_{e_{i-1}}\setminus\\{e_{i-1}\\}$,
which is a contradiction since
$\phi(e_{i-1})\notin\phi(M_{e_{i-1}}\setminus\\{e_{i-1}\\})$. Therefore,
$h_{i}\in T_{6}(e_{i})$ for each $3\leq i\leq k$. This finishes the proof.

###### Claim 9

Let $e=uv$ be a bad edge in $G$. Then there are two vertices $u^{\prime}\in
N(u)$ and $v^{\prime}\in N(v)$ such that $u^{\prime}v^{\prime}\notin E(G)$ and
$|N(uu^{\prime})\cap T_{6}(e)|\geq 2$ or $|N(vv^{\prime})\cap T_{6}(e)|\geq
2$.

Proof. Let $e=uv$ be a bad edge in $G$ with the color $\alpha_{0}$. According
to Claim 4, we may assume that $e_{1}=u_{1}x_{1}\in N_{u}^{2}(e)\cap T_{6}(e)$
and $e_{2}=v_{1}y_{1}\in N_{v}^{2}(e)\cap T_{6}(e)$ are the two distinct
$2$-neighbors of $e$ being colored $\alpha_{0}$, where $u_{1}\in N(u)$ and
$v_{1}\in N(v)$. Denote by $f_{1}$ and $f_{2}$ the two edges $uu_{1}$ and
$vv_{1}$, respectively. For brevity, let $\alpha_{1}=\phi(f_{1})$ and
$\alpha_{2}=\phi(f_{2})$. It is clear that $\alpha_{1}\neq\alpha_{2}$.

First we prove that $T_{6}(e)\setminus\\{e_{1},e_{2}\\}\neq\emptyset$. Suppose
on the contrary that $T_{6}(e)\setminus\\{e_{1},e_{2}\\}=\emptyset$. Recall
that $N^{2}(e)=T_{4}(e)\cup T_{6}(e)$ (see Claim 5), $F(e)=N(e)\cup T_{4}(e)$
and $N^{2-}(e)=F(e)\cup\\{e_{1},e_{2}\\}$. Since $|T_{6}(e)|=2$, by Claim 2(3)
and (5), we have $|F(e)|=|N(e)|+|T_{4}(e)|=(\Delta^{2}-1)-1$ and
$|N(e)|=2(\Delta-1)$. Therefore, $|T_{4}(e)|=(\Delta-1)^{2}-1$. This implies
that, for each $u^{\prime}\in N(u)\setminus\\{v\\}$ and each $v^{\prime}\in
N(v)\setminus\\{u\\}$, $u^{\prime}v^{\prime}\in E(G)$ except when
$u^{\prime}=u_{1}$ and $v^{\prime}=v_{1}$. In other words, $\\{e_{1},e_{2}\\}$
is an edge cut of $G$. Refer to Figure 6.

Figure 6: The illustration of Claim 9

Since $\phi(e_{1})=\phi(e_{2})$ and $\Delta\geq 3$,
$|\phi(N_{x_{1}}[e_{1}]\cup
N_{y_{1}}[e_{2}]\cup\\{f_{1},f_{2}\\})|\leq|\phi(N_{x_{1}}[e_{1}]\cup
N_{y_{1}}[e_{2}]\\})|+2\leq|N_{x_{1}}[e_{1}]|+|N_{y_{1}}[e_{2}]|-1+2\leq\Delta+\Delta-1+2\leq
2\Delta+1<\Delta^{2}-1$. It follows that there exists some color $\alpha$ in
$[1,\Delta^{2}-1]\setminus\phi(N_{x_{1}}[e_{1}]\cup
N_{y_{1}}[e_{2}]\cup\\{f_{1},f_{2}\\})$. Recall that
$N^{2-}(e)=F(e)\cup\\{e_{1},e_{2}\\}$, by Claims 1 and 2, there is exactly one
edge $g$ in $F(e)$ being colored $\alpha$. Notice that
$|N(g)\cap\\{e_{1},e_{2}\\}|\leq 1$, we may assume that $e_{1}\notin N(g)$.
Now, a new coloring $\psi$ can be obtained by recoloring $f_{1}$ and $f_{2}$
with the same color $\alpha$, $g$ with $\alpha_{2}$ and $e$ with $\alpha_{1}$.
It is easy to see that $\psi$ is a good coloring of $G$. Moreover, it is
straightforward to check that
$\kappa_{1}(\psi,\alpha_{0})=\kappa_{1}(\phi,\alpha_{0})-1$ and
$\kappa_{1}(\psi,\beta)\leq\kappa_{1}(\phi,\beta)$ for any color
$\beta\in[1,\Delta^{2}-1]\setminus\\{\alpha_{0}\\}$. Therefore,
$\kappa_{1}(\psi)<\kappa_{1}(\phi)$, contradicting the $1$-optimality of
$\phi$. Thus we must have $T_{6}(e)\setminus\\{e_{1},e_{2}\\}\neq\emptyset$.

It follows from $T_{6}(e)\setminus\\{e_{1},e_{2}\\}\neq\emptyset$ and
$|T_{6}(e)\cap N^{2}_{u}(e)|=|T_{6}(e)\cap N^{2}_{v}(e)|$ (see Observation 5)
that there exists one vertex $u^{\prime}\in N(u)$ such that
$(N(uu^{\prime})\cap T_{6}(e))\setminus\\{e_{1}\\}\neq\emptyset$. Without loss
of generality, let $e_{3}=u^{\prime}x^{\prime}\in(N(uu^{\prime})\cap
T_{6}(e))\setminus\\{e_{1}\\}$. Since $d(u^{\prime})=\Delta$ (see Claim 2(5))
and $e_{3}=u^{\prime}x^{\prime}\in T_{6}(e)$,
$|N(u^{\prime})\cap(N(v)\setminus\\{u\\})|\leq\Delta-2$. Therefore, there
exists one vertex $v^{\prime}\in N(v)$ such that $u^{\prime}v^{\prime}\notin
E(G)$. This implies that there is one edge $e_{4}=v^{\prime}y^{\prime}\in
N(vv^{\prime})\cap T_{6}(e)$. We may assume that $N(uu^{\prime})\cap
T_{6}(e)=\\{e_{3}\\}$ and $N(vv^{\prime})\cap T_{6}(e)=\\{e_{4}\\}$ as
otherwise we are done. It follows that $u^{\prime}\neq u_{1}$, $u^{\prime}p\in
E(G)$ for any $p\in N(v)\setminus\\{v^{\prime}\\}$ and $v^{\prime}q\in E(G)$
for any $q\in N(u)\setminus\\{u^{\prime}\\}$.

A similar argument as above shows that there exists one vertex
$v^{\prime\prime}\in N(v)$ such that $u_{1}v^{\prime\prime}\notin E(G)$ and
there is one edge $e^{\prime\prime}=v^{\prime\prime}y^{\prime\prime}\in
N(vv^{\prime\prime})\cap T_{6}(e)$. It is clear that $v^{\prime\prime}\neq
v^{\prime}$. We may also assume that $N(uu_{1})\cap T_{6}(e)=\\{e_{1}\\}$ and
$N(vv^{\prime\prime})\cap T_{6}(e)=\\{e^{\prime\prime}\\}$. This implies that,
$u_{1}p\in E(G)$ for any $p\in N(v)\setminus\\{v^{\prime\prime}\\}$ and
$v^{\prime\prime}q\in E(G)$ for any $q\in N(u)\setminus\\{u_{1}\\}$. It is
possible that $e_{2}\in\\{e_{4},e^{\prime\prime}\\}$. However, this will not
affect the following arguments.

For convenience, let $\alpha_{3}=\phi(uu^{\prime})$,
$\alpha_{4}=\phi(vv^{\prime})$ and $\alpha_{5}=\phi(vv^{\prime\prime})$. Since
$Q_{1}=vuu^{\prime}$ is an induced path in $G$ and
$uu_{1},vv^{\prime\prime}\in N(uu^{\prime})\cup
N^{2}_{u^{\prime}}(uu^{\prime})$, by Claim 7,
$\alpha_{1},\alpha_{5}\notin\phi(N_{x^{\prime}}[e_{3}])$. Similarly,
$\alpha_{1},\alpha_{5}\notin\phi(N_{y^{\prime}}[e_{4}])$ as
$Q_{2}=uvv^{\prime}$ is an induced path in $G$. Since both $Q_{3}=vuu_{1}$ and
$Q_{4}=uvv^{\prime\prime}$ are induced paths in $G$,
$\alpha_{3},\alpha_{4}\notin\phi(N_{x_{1}}[e_{1}])\cup\phi(N_{y^{\prime\prime}}[e^{\prime\prime}])$.
Now, we recolor $e$ with $\alpha_{1}$, $uu^{\prime}$ and $vv^{\prime}$ with
the same color $\alpha_{5}$, $uu_{1}$ with $\alpha_{3}$ and
$vv^{\prime\prime}$ with $\alpha_{4}$. This gives rise to a new coloring
called $\sigma$. It is easy to check that $\sigma$ is a good coloring of $G$
and $\kappa_{1}(\sigma)<\kappa_{1}(\phi)$, a contradiction to the
$1$-optimility of $\phi$. Therefore, there are two vertices $u^{\prime}\in
N(v)$ and $v^{\prime}\in N(v)$ such that $u^{\prime}v^{\prime}\notin E(G)$ and
$|N(uu^{\prime})\cap T_{6}(e)|\geq 2$ or $|N(vv^{\prime})\cap T_{6}(e)|\geq
2$. This claim is proved.

Finally, we end the proof of Theorem 2.3 by proving the following lemma.

###### Lemma 4.2

Let $G$ be a graph with maximum degree $\Delta\geq 3$. If
$G\notin\mathcal{G}_{\Delta}$, then $\chi^{\prime}_{ss}(G)\leq\Delta^{2}-1$
and $\chi^{\prime}_{(0,1)}(G)\leq\Delta^{2}-1$.

Proof. Let $\phi$ be a $2$-optimal coloring of $G$. By Observation 3, it
suffices to show that $G$ has no bad edge with respect to $\phi$. Suppose to
the contrary, let $e_{0}=uv$ be a bad edge with respect to $\phi$ in $G$. Let
$\alpha_{0}=\phi(e_{0})$. By Claim 4, let $e_{1}\in N_{u}^{2}(e_{0})\cap
T_{6}(e_{0})$ and $e_{2}\in N_{v}^{2}(e_{0})\cap T_{6}(e_{0})$ be the two
$2$-neighbors of $e_{0}$ being colored $\alpha_{0}$.

According to Claim 9, there are two vertices $u_{1}\in N(u)$ and $v_{1}\in
N(v)$ such that $u_{1}v_{1}\notin E(G)$ and $|N(uu_{1})\cap T_{6}(e_{0})|\geq
2$ or $|N(vv_{1})\cap T_{6}(e_{0})|\geq 2$. Without loss of generality, we may
assume that $|N(vv_{1})\cap T_{6}(e_{0})|\geq 2$. Denote by $g_{1}$ and
$g_{2}$ the two edges $uu_{1}$ and $vv_{1}$, respectively. Since
$u_{1}v_{1}\notin E(G)$, $g_{1}$ and $g_{2}$ do not lie on a common $4$-cycle
in $G$.

For brevity, let $\beta_{1}=\phi(g_{1})$ and $\beta_{2}=\phi(g_{2})$. Since
$C_{e_{0}}^{\Delta}=\emptyset$ (refer to Claim 2(4)), $Q_{1}=vuu_{1}$ and
$Q_{2}=uvv_{1}$ are two induced paths in $G$ with $e_{0}$ being a bad edge. By
applying Claim 7 on $Q_{1}=vuu_{1}$ (resp. $Q_{2}=uvv_{1}$), there is exactly
one edge $h_{1}=s_{1}t_{1}$ in $N^{2}_{u_{1}}(g_{1})$ with
$\phi(h_{1})=\beta_{2}$ (resp. $h_{2}=s_{2}t_{2}$ in $N^{2}_{v_{1}}(g_{2})$
with $\phi(h_{2})=\beta_{1}$). Suppose $s_{1}\in N(u_{1})$ and $s_{2}\in
N(v_{1})$. Refer to Figure 7 for the illustration of the coloring $\phi$. We
proceed by proving the following claim.

###### Claim 10

$(1)$ $h_{1}\notin N^{2-}(e_{0})$, $h_{1}\notin N^{2-}(g_{2})$ and $h_{1}\in
T_{6}(g_{1})$;

$(2)$ $h_{2}\notin N^{2-}(e_{0})$, $h_{2}\notin N^{2-}(g_{1})$ and $h_{2}\in
T_{6}(g_{2})$.

Proof. By symmetry, we only prove (1) here. Because $u_{1}v_{1}\notin E(G)$,
$h_{1}\neq g_{2}$. It follows from Claim 2 that $h_{1}\notin N^{2-}(e_{0})$
since $\phi(h_{1})=\phi(g_{2})=\beta_{2}$ and $g_{2}\in N(e_{0})$. Recall that
$Q_{2}=uvv_{1}$ is an induced path in $G$ with $uv$ being a bad edge, by Claim
8(2), we have $\phi(g_{2})=\beta_{2}\notin\phi(N^{2-}(g_{2}))$. Thus $h_{1}$
being colored with $\beta_{2}$ is not in $N^{2-}(g_{2})$. As $Q_{1}=vuu_{1}$
is an induced path with $vu$ being a bad edge, by Claim 8(1),
$N^{2}(g_{1})=T_{4}(g_{1})\cup T_{6}(g_{1})$. Since $h_{1}\in
N^{2}_{u_{1}}(g_{1})$, $h_{1}$ is either in $T_{4}(g_{1})$ or in
$T_{6}(g_{1})$. If $h_{1}\in T_{4}(g_{1})$, then $h_{1}\in N^{2}(e_{0})$,
which is a contradiction since $h_{1}\notin N^{2-}(e_{0})$. Therefore,
$h_{1}\in T_{6}(g_{1})$. This claim is true.

Figure 7: The illustration of the coloring $\phi$

We use $f_{1}$ and $f_{2}$ to denote the two edges $u_{1}s_{1}$ and
$v_{1}s_{2}$, respectively. It is clear that $f_{1},f_{2}\in N^{2}(e_{0})$.
Notice that $N^{2}(e_{0})=T_{4}(e_{0})\cup T_{6}(e_{0})$ (see Claim 5), by
Claim 10, we must have $f_{1},f_{2}\in T_{6}(e_{0})$ and
$u_{1}s_{2},u_{1}t_{2},v_{1}s_{1},v_{1}t_{1}\notin E(G)$. Recall that
$|N(g_{2})\cap T_{6}(e)|\geq 2$, there exists one edge
$f_{3}=v_{1}s_{3}\in(N(g_{2})\cap T_{6}(e_{0}))\setminus\\{f_{2}\\}$. It is
possible that $e_{2}\in\\{f_{2},f_{3}\\}$. However, this will not affect the
following arguments.

For convenience, let $\alpha_{i}=\phi(f_{i})$ for each $i\in[1,3]$. By Claim
2, it is clear that
$\\{\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3}\\}\cap\\{\beta_{1},\beta_{2}\\}=\emptyset$,
$\beta_{1}\neq\beta_{2}$ and $\alpha_{2}\neq\alpha_{3}$. Moreover, it follows
from $f_{2}\in T_{6}(e_{0})$ that $Q_{3}=uvv_{1}s_{2}$ is an induced path in
$G$ with $uv$ being a bad edge, where $g_{2}=vv_{1}$ and $f_{2}=v_{1}s_{2}$.
Since $\phi(g_{2})=\beta_{2}$, by Claim 8(3), there is exactly one edge
$p_{1}=r_{1}r_{1}^{\prime}$ in $N^{2}_{s_{2}}(f_{2})$ being colored
$\beta_{2}$ and $p_{1}\in T_{6}(f_{2})$, where $r_{1}\in N(s_{2})$.
Analogously, as $f_{3}\in T_{6}(e_{0})$ and $Q_{4}=uvv_{1}s_{3}$ is an induced
path in $G$, exactly one edge $p_{2}=r_{2}r_{2}^{\prime}$ in
$N^{2}_{s_{3}}(f_{3})$ with $r_{2}\in N(s_{3})$ is colored $\beta_{2}$ and
$p_{2}\in T_{6}(f_{3})$. Recall that $f_{2}\in T_{6}(e_{0})\cap
N_{v}^{2}(e_{0})$ and $\phi(f_{2})=\alpha_{2}$, by Observation 5, there is
exactly one edge $f_{2}^{\prime}=u^{\prime}x^{\prime}$ in $T_{6}(e_{0})\cap
N^{2}_{u}(e_{0})$ with the color $\alpha_{2}$ under $\phi$, where
$u^{\prime}\in N(u)$. Possibly $f_{2}^{\prime}=f_{1}$. But whether they are
distinct or not will not affect the following arguments. We then prove the
claim below.

###### Claim 11

Let $w$ be any vertex in $N(v_{1})$. If $v_{1}w\in T_{6}(e_{0})$, then
$s_{1}w\notin E(G)$.

Proof. Let $w$ be a vertex in $N(v_{1})$ such that $v_{1}w\in T_{6}(e_{0})$.
Suppose that $s_{1}w\in E(G)$. Recall that $f_{1}=u_{1}s_{1}\in T_{6}(e_{0})$,
$Q_{5}=vuu_{1}s_{1}$ is an induced path with $vu$ being a bad edge. Then by
Claim 8(1), $C_{f_{1}}^{\Delta}=\emptyset$ and so $u_{1}w\notin E(G)$ as
$s_{1}w\in E(G)$. And it follows from $v_{1}w\in T_{6}(e_{0})$ that $uw\notin
E(G)$ and $vw\notin E(G)$. Therefore, $Q_{6}=vuu_{1}s_{1}w$ is also an induced
path in $G$. Since $h_{1}\notin N^{2-}(g_{2})$ (see Claim 10), $h_{1}\neq
s_{1}w$ and so $h_{1}\in N(s_{1}w)\setminus\\{f_{1}\\}$. As $g_{2}\in
N_{w}^{2}(s_{1}w)$, by Claim 7, we must have $\phi(h_{1})\neq\phi(g_{2})$.
This contradicts the fact that $\phi(h_{1})=\phi(g_{2})=\beta_{2}$. Therefore,
$s_{1}w\notin E(G)$.

Claim 11 implies that $s_{1}s_{2},s_{1}s_{3}\notin E(G)$. The remainder of the
proof is divided into the following two cases according to whether edges
$p_{1}$ and $p_{2}$ are different from $h_{1}$ or not.

Case 1. $p_{1}\neq h_{1}$ or $p_{2}\neq h_{1}$.

By symmetry, we may assume that $p_{1}\neq h_{1}$. It follows that
$s_{2}t_{1}\notin E(G)$. In other words, the distance between $h_{1}$ and
$f_{2}$ is at least $3$. Then we can obtain a new coloring $\sigma$ of $G$ by
recoloring $g_{1}$ and $f_{2}$ with the same color $\beta_{2}$, $g_{2}$ with
$\beta_{1}$ and $e_{0}$ with $\alpha_{2}$ (possibly $\alpha_{2}=\alpha_{0}$),
as illustrated in Figure 8. It is easy to verify that $\sigma$ is a good
coloring of $G$. In the following, we will show that
$\kappa_{1}(\sigma)<\kappa_{1}(\phi)$, which contradicts the $1$-optimality of
$\phi$.

Figure 8: The illustration of Case 1

Firstly, because $\sigma(f_{2})=\beta_{2}$, the edge $f_{2}^{\prime}$ is the
only $2$-neighbor of $e_{0}$ colored $\alpha_{2}$ under $\sigma$. Thus, the
edge $e_{0}$ is not a bad edge with respect to $\sigma$ as $f_{2}^{\prime}\in
T_{6}(e_{0})$. And since $f_{2}^{\prime}=u^{\prime}x^{\prime}\in
T_{6}(e_{0})$, $Q_{7}=vuu^{\prime}x^{\prime}$ is an induced path in $G$. Then
by Claim 8(2), the edge $e_{0}$ is the only $2$-neighbor of $f_{2}^{\prime}$
colored $\alpha_{2}$ under $\sigma$. Hence, the edge $f_{2}^{\prime}$ is also
not a bad edge with respect to $\sigma$.

Secondly, since $g_{1},g_{2}\in N(e_{0})$, by Claim 6, there is no edge in
$N^{2}(e_{0})$ being colored $\beta_{1}$ or $\beta_{2}$ under $\phi$. Recall
that $h_{1}=s_{1}t_{1}$ is the only edge in $N^{2}_{u_{1}}(g_{1})$ with
$\phi(h_{1})=\beta_{2}$ and $f_{2}\notin N^{2-}(g_{1})$ (see Claim 10),
$h_{1}$ is the only $2$-neighbor of $g_{1}$ colored $\beta_{2}$ under
$\sigma$. Due to Claim 10, $Q_{8}=vuu_{1}s_{1}t_{1}$ is an induced path in
$G$. Thus by Claim 8(2), $\phi(h_{1})=\beta_{2}\notin\phi(N^{2-}(h_{1}))$ and
so $g_{1}$ is the only $2$-neighbor of $h_{1}$ colored $\beta_{2}$ under
$\sigma$. Therefore, both $g_{1}$ and $h_{1}$ are not bad edges with respect
to $\sigma$. A similar argument shows that $g_{2}$ and $h_{2}$ are not bad
edges with respect to $\sigma$.

Thirdly, recall that $Q_{3}=uvv_{1}s_{2}$ is an induced path in $G$, by Claim
8(3), no edge in $N^{2-}(g_{2})$ is colored $\phi(g_{2})=\beta_{2}$ under
$\phi$. Since $\phi(p_{1})=\beta_{2}$, $p_{1}\notin N^{2-}(g_{2})$. This,
together with $p_{1}=r_{1}r_{1}^{\prime}\in T_{6}(f_{2})$, implies that
$Q_{9}=uvv_{1}s_{2}r_{1}r_{1}^{\prime}$ is an induced path in $G$. Again by
Claims 7 and 8(3), $p_{1}$ is the only $2$-neighbor of $f_{2}$ colored
$\beta_{2}$ under $\sigma$ and $f_{2}$ is the only $2$-neighbor of $p_{1}$
colored $\beta_{2}$ under $\sigma$. Thus the two edges $f_{2}$ and $p_{1}$ are
not bad edges with respect to $\sigma$.

Finally, if $p_{2}\in\\{h_{1},p_{1}\\}$, then $p_{2}$ is obviously not a bad
edge with respect to $\sigma$. And if $p_{2}\notin\\{h_{1},p_{1}\\}$, then
$Q_{10}=uvv_{1}s_{3}r_{2}r_{2}^{\prime}$ is an induced path in $G$ as
$p_{2}=r_{2}r_{2}^{\prime}\in T_{6}(f_{3})$ and $\phi(p_{2})=\beta_{2}$. By
Claim 8(3), $p_{2}$ has no $2^{-}$-neighbor with the color $\beta_{2}$ and
thus it is not a bad edge with respect to $\sigma$. Combining the above
discussions, we conclude that $\kappa_{1}(\sigma)<\kappa_{1}(\phi)$.

Case 2. $p_{1}=p_{2}=h_{1}$.

In this case, we must have $s_{2}t_{1},s_{3}t_{1}\in E(G)$ as
$s_{1}s_{2},s_{1}s_{3}\notin E(G)$. Refer to Figure 9. Let
$\gamma=\phi(s_{3}t_{1})$. Recall that $Q_{2}=uvv_{1}$ is induced, we must
have $\gamma\notin\\{\beta_{1},\beta_{2},\alpha_{2}\\}$ due to Claim 7. Now,
we recolor $g_{1}$ with $\beta_{2}$, $g_{2}$ with $\beta_{1}$, $e_{0}$ and
$s_{3}t_{1}$ with the same color $\alpha_{2}$ (possibly
$\alpha_{2}=\alpha_{0}$) and $f_{2}$ with $\gamma$. This yields a new coloring
of $G$ called $\sigma$. Similar to the arguments in the proof of Case 1, it is
easy to check that $\sigma$ is a good coloring of $G$ and the six edges
$e_{0},f_{2}^{\prime},g_{1},g_{2},h_{1},h_{2}$ are not bad edges with respect
to $\sigma$.

Figure 9: The illustration of Case 2

Notice that $s_{3}t_{1}\in T_{4}(f_{2})$ and $Q_{3}=uvv_{1}s_{2}$ is an
induced path in $G$, by Claim 7, no edge in
$N^{2-}(f_{2})\setminus\\{s_{3}t_{1},e_{0}\\}$ being colored $\gamma$ under
$\phi$ and so $f_{2}$ has no $2^{-}$-neighbor being colored $\gamma$ under
$\sigma$. That is, $f_{2}$ is not a bad edge with respect to $\sigma$. Recall
that $h_{1}=s_{1}t_{1}\notin N^{2-}(e_{0})\cup N^{2-}(g_{2})$ (see Claim 10),
$t_{1}u,t_{1}v,t_{1}v_{1}\notin E(G)$. This, together with the induced path
$Q_{4}=uvv_{1}s_{3}$, implies that $Q_{11}=uvv_{1}s_{3}t_{1}$ is also induced
and $s_{3}t_{1}\notin N^{2-}(e_{0})$. Then by Claim 7, $f_{2}$ is the only
edge in $N^{2-}(s_{3}t_{1})$ being colored $\alpha_{2}$ under $\phi$.
Therefore, $s_{3}t_{1}$ has no $2^{-}$-neighbor being colored $\alpha_{2}$
under $\sigma$ and so it is not a bad edge with respect to $\sigma$.
Therefore, it holds that $\kappa_{1}(\sigma)<\kappa_{1}(\phi)$.

We have deduced contradictions in both cases. Therefore, there is no bad edge
with respect to $\phi$ in $G$. By Observation 3, $\phi$ is both a semistrong
edge coloring and a $(0,1)$-relaxed strong edge coloring using at most
$\Delta^{2}-1$ colors. This completes the proof of this lemma.

Theorem 2.3 follows from Lemmas 4.1 and 4.2, which implies Theorems 1.4 and
1.5.

##  5 Summary

In this paper, we showed that the semistrong chromatic index of a connected
graph with maximum degree $\Delta$ is at most $\Delta^{2}-1$, except $C_{7}$
and $K_{\Delta,\Delta}$. This upper bound is tight as the upper bound $3$ is
the best possible for the case $\Delta=2$. Moreover, as indicated by Lužar,
Mockovčiaková and Soták in [16], the $5$-prism (see Figure 2) shows the
sharpness of the bound 8 for the case $\Delta=3$. However, they do not find
infinitely many graphs attaining the bound 8. Likewise, we do not find graphs
with maximum degree $\Delta\geq 4$ and their semistrong chromatic indices
being equal to $\Delta^{2}-1$.

For $\Delta=4$, the graph “$C_{7}$-blowup” constructed as follows has the
semistrong chromatic index $\Delta^{2}-2$: the vertex set
$V=\cup_{i=0}^{6}V_{i}$ where each $V_{i}$ is an independent set with two
vertices, and for any two different integers $i,j\in\\{0,1,\dots,6\\}$,
$V_{i}\cap V_{j}=\emptyset$ and each vertex in $V_{i}$ is adjacent to each
vertex in $V_{i+1}$, where indices are modulo 7. Therefore, we believe that
the upper bound $\Delta^{2}-1$ can be further improved. After some
exploration, we propose the following problem.

Problem 1: Let $G$ be a graph with maximum degree $\Delta$. Suppose no
component of $G$ is isomorphic to $K_{\Delta,\Delta}$. If $\Delta$ is
appropriately large, is it true that
$\chi^{\prime}_{ss}(G)\leq\Delta^{2}-\Delta+1$?

It should be pointed out that, the above upper bound if proven, would be the
best possible. Let $H$ denote the graph obtained by taking two copies of
$K_{\Delta-1,\Delta}$ and adding one edge between two distinct vertices of
degree $\Delta-1$ from each of the two copies. Clearly, the maximum degree of
$H$ is $\Delta$. And it is easy to check that
$\chi^{\prime}_{ss}(H)=\Delta^{2}-\Delta+1$. It follows that, any graph $G$
containing $H$ as a subgraph has the semistrong chromatic index at least
$\Delta^{2}-\Delta+1$.

Meanwhile, we also proved that the $(0,1)$-relaxed strong chromatic index of a
connected graph with maximum degree $\Delta$ is at most $\Delta^{2}-1$, except
$C_{7}$. However, we tried without success finding a graph whose
$(0,1)$-relaxed strong chromatic index is close to $\Delta^{2}-1$. We strongly
believe that this upper bound is not tight and propose the following
conjecture.

###### Conjecture 5.1

For each connected graph $G$ with maximum degree $\Delta$ other than $C_{7}$,

$\chi^{\prime}_{(0,1)}(G)\leq\begin{cases}\begin{array}[]{cl}\lceil\dfrac{5}{8}\Delta^{2}\rceil,&\text{if}\
\Delta\ \text{is even,}\\\
\lceil\dfrac{5}{8}\Delta^{2}-\dfrac{1}{4}\Delta+\dfrac{1}{8}\rceil,&\text{if}\
\Delta\ \text{is odd.}\end{array}\end{cases}$

The graphs “$C_{5}$-blowups” constructed by Erdős and Nešetřil [6, 7] indicate
that the bounds given in Conjecture 5.1, if proven, would be tight. Moreover,
the bounds in Conjecture 5.1 are about half the bounds in Erdős and Nešetřil’s
conjecture (see Conjecture 1.1). This reveals that a little relaxation can
save a large proportion of colors. Therefore, it would be quite significant to
study the $(s,t)$-relaxed strong edge coloring of graphs, which will help to
greatly save channel resources in the channel assignment problem of wireless
radio networks.

ACKNOWLEDGMENTS

The research was supported by National Natural Science Foundation of China
11771080.

## References

  * [1] L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discret. Math. 108 (1992), 231-252.
  * [2] J. Baste and D. Rautenbach, Degenerate matchings and edge colorings, Discrete Appl. Math. 239 (2018), 38-44.
  * [3] M. Bonamy, T. Perrett, and L. Postle, Colouring graphs with sparse neighbourhoods: Bounds and applications, J. Comb. Theory Ser. B 155 (2022), 278-317.
  * [4] H. Bruhn and F. Joos, A stronger bound for the strong chromatic index, Electron. Notes Discret. Math. 49 (2015), 277-284.
  * [5] A. A. Diwan, The minimum forcing number of perfect matchings in the hypercube, Discret. Math. 342 (2019), no. 4, 1060-1062.
  * [6] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discret. Math. 72 (1988), 81-92.
  * [7] P. Erdős and J. Nešetřil, Problems, In: Halász, G., Sós, V.T. (eds.) Irregularities of Partitions, pp. 162-163, Springer, Berlin, 1989.
  * [8] R. J. Faudree, R. H. Schelp, A. Gyárfás, and Zs. Tuza, The strong chromatic index of graphs, Ars Comb. 29B (1990), 205-211.
  * [9] J. L. Fouquet and J. L. Jolivet, Strong edge-colorings of graphs and applications to multi-$k$-gons, Ars Comb. 16A (1983), 141-150.
  * [10] W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, and R. Laskar, Generalized subgraph-restricted matchings in graphs, Discret. Math. 293 (2005), no. 1-3, 129-138.
  * [11] A. Gyárfás and A. Hubenko, Semistrong edge coloring of graphs, J. Graph Theory 49 (2005), no. 1, 39-47.
  * [12] D. He and W. Lin, On $(s,t)$-relaxed strong edge-colorings of graphs, J. Comb. Optim. 33 (2017), 609-625.
  * [13] H. Hocquard, D. Lajou, and B. Lužar, Between proper and strong edge-colorings of subcubic graphs, J. Graph Theory 101 (2022), 686-716.
  * [14] P. Horák, H. Qing, and W. T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993), no. 2, 151-160.
  * [15] E. Hurley, R. de Joannis de Verclos, and R. J. Kang, An improved procedure for colouring graphs of bounded local density, In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 135-148, 2021. https://arxiv.org/abs/2007.07874.
  * [16] B. Lužar, M. Mockovčiaková, and R. Soták, Revisiting semistrong edge-coloring of graphs, arXiv preprint, 2022. arXiv:2208.13297.
  * [17] M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Comb. Theory Ser. B 69 (1997), no. 2, 103-109.
  * [18] T. Nandagopal, T. Kim, X. Gao, and V. Bharghavan, Achieving MAC layer fairness in wireless packet networks, In Proceedings of the 6th annual international conference on Mobile computing and networking, pp. 87-98, 2000.
  * [19] S. Ramanathan, A unified framework and algorithm for (T/F/C) DMA channel assignment in wireless networks, In Proceedings of INFOCOM’97, IEEE, 2 (1997), 900-907.


$|\theta|<\kappa_{1},\quad\textrm{where}\quad\kappa_{1}:=\frac{2|b_{3,0}|}{|a_{0,1}-c_{0,1}|},$
(6.21)

which is well-defined by Lemma 6.2. Thus, we have shown that
$\Delta(\varepsilon,\delta)>0$ if $\varepsilon\neq 0$ is sufficiently small
and

$\delta=\varepsilon^{2}(\kappa_{0}+\varepsilon\theta)=\varepsilon^{2}\kappa_{0}+\varepsilon^{3}\theta\quad\textrm{with}\quad|\theta|<\kappa_{1}.$
(6.22)

Returning to the expression for the eigenvalues (6.12), we find that
$\text{Re}\lambda_{+}=\frac{1}{2}\sqrt{\Delta(\varepsilon,\delta)}>0$.
Therefore, small-amplitude Stokes waves are unstable with respect to
transverse perturbations with wave numbers $\alpha=\sqrt{\beta_{*}+\delta}$
for any
$\delta\in(\varepsilon^{2}\kappa_{0}-\varepsilon^{3}\kappa_{1},\varepsilon^{2}\kappa_{0}+\varepsilon^{3}\kappa_{1})$,
provided $\varepsilon$ is sufficiently small. Finally, since

$\Delta(\varepsilon,\delta)=\varepsilon^{6}\Delta^{\prime\prime\prime}(\varepsilon,\theta)=\varepsilon^{6}\left[4b_{3,0}^{2}-(a_{0,1}-c_{0,1})^{2}\theta^{2}\right]+O(\varepsilon^{7}),$
(6.23)

we have $\text{Re}\lambda_{+}=O(\varepsilon^{3})$ as $\varepsilon\rightarrow
0$, completing the proof. ∎

######  Corollary 6.3.

For sufficiently small $\varepsilon$, the curve
$(-\kappa_{1},\kappa_{1})\ni\theta\mapsto\lambda_{+}(\varepsilon,\theta)$
(resp.
$(-\kappa_{1},\kappa_{1})\ni\theta\mapsto\lambda_{-}(\varepsilon,\theta)$) is
within $O(\varepsilon^{4})$ distance to the entire right (resp. left) half of
the ellipse

$\displaystyle\frac{\lambda_{r}^{2}}{\left(b_{3,0}\varepsilon^{3}\right)^{2}}+\frac{\left(\lambda_{i}-\sigma-\left(\frac{a_{0,1}c_{2,0}-a_{2,0}c_{0,1}}{(a_{0,1}-c_{0,1})}\right)\varepsilon^{2}\right)^{2}}{\left(\frac{b_{3,0}(a_{0,1}+c_{0,1})}{a_{0,1}-c_{0,1}}\varepsilon^{3}\right)^{2}}=1$
(6.24)

in the complex plane.

###### Proof.

We begin with the expansion of $\Delta(\varepsilon,\delta)$ given in (6.23) as
well as the expansion

$\displaystyle A+C$
$\displaystyle=(a_{0,1}+c_{0,1})\delta+(a_{2,0}+c_{2,0})\varepsilon^{2}+O(\varepsilon^{4})$
(6.25)
$\displaystyle=\frac{2(a_{0,1}c_{2,0}-a_{2,0}c_{0,1})}{a_{0,1}-c_{0,1}}\varepsilon^{2}+(a_{0,1}+c_{0,1})\theta\varepsilon^{3}+O(\varepsilon^{4}),$

where we have used (6.22) to replace $\delta$. Substituting both of these
expansions into the formula for the unstable eigenvalues given by (6.12), we
obtain the expansion

$\displaystyle\lambda_{\pm}\equiv\lambda_{\pm}(\varepsilon,\theta)$
$\displaystyle=i\left[\sigma+\frac{a_{0,1}c_{2,0}-a_{2,0}c_{0,1}}{(a_{0,1}-c_{0,1})}\varepsilon^{2}+\frac{a_{0,1}+c_{0,1}}{2}\theta\varepsilon^{3}\right]$
(6.26)
$\displaystyle\qquad\pm\frac{1}{2}\left[4b_{3,0}^{2}-(a_{0,1}-c_{0,1})^{2}\theta^{2}\right]^{\frac{1}{2}}|\varepsilon|^{3}+O(\varepsilon^{4}).$

For sufficiently small $\varepsilon$ and for $\theta$ satisfying (6.21), it
follows from (6.26) that $\lambda_{+}(\varepsilon,\theta)$ is within
$O(\varepsilon^{4})$ distance to $(\lambda_{r},\lambda_{i})\in\mathbb{R}^{2}$,
where

$\displaystyle\lambda_{r}$
$\displaystyle=\frac{1}{2}\left[4b_{3,0}^{2}-(a_{0,1}-c_{0,1})^{2}\theta^{2}\right]^{\frac{1}{2}}|\varepsilon|^{3},$
$\displaystyle\lambda_{i}$
$\displaystyle=\sigma+\frac{a_{0,1}c_{2,0}-a_{2,0}c_{0,1}}{2(a_{0,1}-c_{0,1})}\varepsilon^{2}+\frac{a_{0,1}+c_{0,1}}{2}\theta\varepsilon^{3}.$

By eliminating $\theta$ from the preceding expressions, we find that
$(\lambda_{r},\lambda_{i})$ lies on the ellipse (6.24). We note that, as
$\theta$ varies in the interval $(-\kappa_{1},\kappa_{1})$,
$(\lambda_{r},\lambda_{i})$ traces the entire right half of the ellipse
(6.24). Lastly, we note that if the coefficients above are numerically
evaluated, we obtain the ellipse (1.3) given in the introduction. ∎

##  Appendix A Stokes expansion

We recall the water wave system with zero Bernoulli constant:

$\displaystyle\Delta_{x,y}\phi=0\quad\text{in }\Omega,$ (A.1)
$\displaystyle-c\partial_{x}\phi+g\eta+\tfrac{1}{2}|\nabla_{x,y}\phi|^{2}=0\quad\text{
on }\\{y=\eta(x)\\},$ (A.2)
$\displaystyle\partial_{y}\phi+(c-\partial_{x}\phi)\partial_{x}\eta=0\quad\text{
on }\\{y=\eta(x)\\},$ (A.3) $\displaystyle\nabla_{x,y}\phi\to 0\text{ as
}y\to-\infty.$ (A.4)

Using superscripts we Taylor-expand the unknowns,

$\displaystyle\eta=\varepsilon\eta^{1}+\varepsilon^{2}\eta^{2}+\varepsilon^{3}\eta^{3}+\varepsilon^{4}\eta^{4}\dots,$
$\displaystyle\phi=\varepsilon\phi^{1}+\varepsilon^{2}\phi^{2}+\varepsilon^{3}\phi^{3}+\varepsilon^{4}\phi^{4}+\dots,$
$\displaystyle c=c^{0}+\varepsilon
c^{1}+\varepsilon^{2}c^{2}+\varepsilon^{3}c^{3}+\dots,$

and reserve subscripts for derivatives. Here
$\phi^{j}(x,y):\mathbb{R}\times\mathbb{R}_{-}\to\mathbb{R}$. It was found in
[28] that

$\displaystyle\eta^{1}=\cos
x,\quad\eta^{2}=\frac{1}{2}\cos(2x),\quad\eta^{3}=\frac{1}{8}\cos
x+\frac{3}{8}\cos(3x),$ (A.5)
$\displaystyle\phi^{1}=\sqrt{g}e^{y}\sin(x),\quad\phi^{2}=\phi^{3}=0,$
$\displaystyle c^{0}=\sqrt{g},\quad c^{1}=0,\quad c^{2}=\frac{\sqrt{g}}{2}.$

Our goal is to find the next coefficients $c^{3}$, $\eta^{4}$ and $\phi^{4}$.
The coefficient of $\varepsilon^{4}$ in (A.2) is

$\displaystyle-c^{0}(\phi_{x})^{4}-c^{2}(\phi_{x})^{2}-c^{3}(\phi_{x})^{1}+g\eta^{4}+\frac{1}{2}|(\nabla_{x,y}\phi)^{2}|+(\nabla_{x,y}\phi)^{1}\cdot(\nabla_{x,y}\phi)^{3}$
$\displaystyle=-c^{0}\left\\{\phi^{4}_{x}+\phi^{3}_{xy}\eta^{1}+\phi^{2}_{xy}\eta^{2}+\phi^{1}_{xy}\eta^{3}+\frac{1}{2}\phi^{2}_{xyy}\eta^{1}\eta^{1}+\phi^{1}_{xyy}\eta^{1}\eta^{2}+\frac{1}{6}\phi^{1}_{xyyy}\eta^{1}\eta^{1}\eta^{1}\right\\}$
$\displaystyle\quad-c^{2}(\phi^{2}_{x}+\phi^{1}_{xy}\eta^{1})-c^{3}\phi^{1}_{x}+g\eta^{4}+\frac{1}{2}[\phi^{2}_{x}+\phi^{1}_{xy}\eta^{1}]^{2}+\frac{1}{2}[\phi^{2}_{y}+\phi^{1}_{yy}\eta^{1}]^{2}$
$\displaystyle\quad+\phi^{1}_{x}\phi^{1}_{xy}\eta^{2}+\frac{1}{2}\phi^{1}_{x}\phi^{1}_{xyy}\eta^{1}\eta^{1}+\phi^{1}_{y}\phi^{1}_{yy}\eta^{2}+\frac{1}{2}\phi^{1}_{y}\phi^{1}_{yyy}\eta^{1}\eta^{1}.$

Substituting (A.5) then equating this to $0$, we obtain

$\phi^{4}_{x}+c^{0}\left\\{-\frac{1}{6}\cos(2x)+\frac{1}{3}\cos(4x)\right\\}+c^{3}\cos
x-\sqrt{g}\eta^{4}=0$ (A.6)

at $y=0$. Next we calculate the coefficient of $\varepsilon^{4}$ in (A.3)

$\displaystyle(\phi_{y}\phi)^{4}+c^{0}\eta_{x}^{4}+c^{2}\eta_{x}^{2}+c^{3}\eta^{1}_{x}-(\phi_{x})^{1}\eta_{x}^{3}-(\phi_{x})^{2}\eta_{x}^{2}-(\phi_{x})^{3}\eta_{x}^{1}$
(A.7)
$\displaystyle=\phi^{4}_{y}+\phi^{3}_{yy}\eta^{1}+\phi^{2}_{yy}\eta^{2}+\phi^{1}_{yy}\eta^{3}+\frac{1}{2}\phi^{2}_{yyy}\eta^{1}\eta^{1}+\phi^{1}_{yyy}\eta^{1}\eta^{2}+\frac{1}{6}\phi^{1}_{yyyy}\eta^{1}\eta^{1}\eta^{1}$
$\displaystyle\quad+c^{0}\eta^{4}_{x}+c^{2}\eta^{2}_{x}+c^{3}\eta^{1}_{x}-\phi^{1}_{x}\eta^{3}_{x}-\eta^{2}_{x}(\phi^{2}_{x}+\phi^{1}_{xy}\eta^{1})-\eta^{1}_{x}\left\\{\phi^{3}_{x}+\phi^{2}_{xy}\eta^{1}+\phi^{1}_{xy}\eta^{2}+\frac{1}{2}\phi^{1}_{xyy}\eta^{1}\eta^{1}\right\\}$
$\displaystyle=\phi_{y}^{4}+c^{0}\left\\{\frac{2}{3}\sin(2x)+\frac{4}{3}\sin(4x)\right\\}+c^{0}\eta_{x}^{4}-c^{3}\sin
x,\quad y=0.$

Differentiating (A.6) in $x$ then adding to (A.7) we obtain the boundary
condition for $\phi$

$\phi^{4}_{xx}+\phi^{4}_{y}+\sqrt{g}\sin(2x)-2c^{3}\sin x=0,\quad y=0.$ (A.8)

In addition, we have in view of (A.1) and (A.4) that $\Delta_{x,y}\phi^{4}=0$
in $\\{y<0\\}$ and $\nabla_{x,y}\phi\to 0$ as $y\to-\infty$. Choosing
$c^{3}=0$ and seeking the solution of the form $\phi(x,y)=a\sin(2x)e^{by}$
with $b<0$, we find

$\phi^{4}(x,y)=\frac{\sqrt{g}}{2}\sin(2x)e^{2y}.$ (A.9)

Inserting (A.9) in (A.6) gives

$\eta^{4}(x)=\sqrt{g}\left\\{\frac{5}{6}\cos(2x)+\frac{1}{3}\cos(4x)\right\\}.$
(A.10)

Finally, using $\psi(x)=\phi(x,\eta(x))$ we obtain

$\displaystyle\psi^{4}(x)$ $\displaystyle=\varepsilon\sqrt{g}\sin
x+\varepsilon^{2}\frac{\sqrt{g}}{2}\sin(2x)+\varepsilon^{3}\frac{\sqrt{g}}{4}\big{(}3\sin
x\cos(2x)+\sin x\big{)}+$ (A.11)
$\displaystyle\quad+\varepsilon^{4}\sqrt{g}\left\\{\frac{5}{12}\sin(2x)+\frac{1}{3}\sin(4x)\right\\}+O(\varepsilon^{5}).$

##  Appendix B Proof of Proposition 2.9

We recall from Remark 2.5 that $\zeta$ is analytic in $\varepsilon$ with
values in Sobolev spaces. From (2.57) and (2.14) we have

$p=\frac{c_{*}-\zeta_{\sharp}V_{*}}{\zeta^{\prime}},\quad
q=-p\partial_{x}(\zeta_{\sharp}B_{*}),$

where

$B^{*}=\frac{G(\eta^{*})\psi^{*}+\partial_{x}\psi^{*}\partial_{x}\eta^{*}}{1+|\partial_{x}\eta^{*}|^{2}},\qquad
V^{*}=\partial_{x}\psi^{*}-B^{*}\partial_{x}\eta^{*}.$

By Theorem 1.2 in [5], for any $s>\frac{5}{2}$, the mapping

$H^{s}(\mathbb{T})\ni\eta\mapsto G(\eta)\in\mathcal{L}(H^{s},H^{s-1})$ (B.1)

is analytic on any bounded set. Combining this with the analyticity in
$\varepsilon$ of $\eta^{*}$ and $\psi^{*}$ and the boundedness of the
Dirichlet-Neumann operator, we deduce that $B^{*}$ and $V^{*}$ are analytic in
$\varepsilon$ with values in Sobolev spaces. In conjunction with analyticity
in $\varepsilon$ of $c_{*}$ and $\zeta$, this yields analyticity in
$\varepsilon$ of $p$ and $q$ and $\frac{1+q}{\zeta^{\prime}}$. The remainder
of this proof is devoted to expansions in powers of $\varepsilon$ for these
analytic functions.

###  B.1. Shape-derivative

We view $G(\eta)\psi$ as a linear operator with respect to $\psi$. Let
$G^{\prime}(\eta)\overline{\eta}\psi$ denote the shape-derivative of
$G(\eta)\psi$ with respect to $\eta$ evaluated at $\overline{\eta}$. We recall
from Theorem 2.3 that the shape-derivative is given by

$G^{\prime}(\eta)\overline{\eta}\psi=-G(\eta)(\overline{\eta}B(\eta)\psi)-\partial_{x}(\overline{\eta}V(\eta)\psi),$
(B.2)

where

$B(\eta)\psi=\frac{G(\eta)\psi+\partial_{x}\psi\partial_{x}\eta}{1+|\partial_{x}\eta|^{2}},\qquad
V(\eta)\psi=\partial_{x}\psi-\partial_{x}\eta B(\eta)\psi.$ (B.3)

Again, we view $B(\eta)\psi$ and $V(\eta)\psi$ as linear operators with
respect to $\psi$. Next, to calculate the second derivative
$G^{\prime\prime}(\eta)\psi$ we reapply (B.2) and obtain

$G^{\prime\prime}(\eta)[\overline{\eta},\widetilde{\eta}]\psi=-G^{\prime}(\eta)\widetilde{\eta}(\overline{\eta}B(\eta,\psi))-G(\eta)(\overline{\eta}B^{\prime}(\eta)\widetilde{\eta}\psi)+\partial_{x}\\{\overline{\eta}\partial_{x}\eta
B^{\prime}(\eta)\widetilde{\eta}\psi+\overline{\eta}\partial_{x}\widetilde{\eta}B(\eta)\psi\\},$
(B.4)

where

$B^{\prime}(\eta)\widetilde{\eta}\psi=\frac{1}{1+|\partial_{x}\eta|^{2}}\\{G^{\prime}(\eta)\widetilde{\eta}\psi+\partial_{x}\widetilde{\eta}\partial_{x}\psi\\}-\frac{2\partial_{x}\eta\partial_{x}\widetilde{\eta}}{(1+|\partial_{x}\eta|^{2})^{2}}\\{G(\eta)\psi+\partial_{x}\eta\partial_{x}\psi\\}.$
(B.5)

Now substituting $\eta=0$ yields

$\displaystyle G(0)=|D|,\quad B(0)=|D|,\quad V(0)=\partial_{x},$ (B.6)
$\displaystyle
G^{\prime}(0)\overline{\eta}\psi=-|D|(\overline{\eta}|D|\psi)-\partial_{x}(\overline{\eta}\partial_{x}\psi),$

whence

$B^{\prime}(0)\widetilde{\eta}\psi=G^{\prime}(0)\widetilde{\eta}\psi+\partial_{x}\widetilde{\eta}\partial_{x}\psi=-|D|(\widetilde{\eta}|D|\psi)-\partial_{x}(\widetilde{\eta}\partial_{x}\psi)+\partial_{x}\widetilde{\eta}\partial_{x}\psi$
(B.7)

and

$\displaystyle G^{\prime\prime}(0)[\overline{\eta},\widetilde{\eta}]\psi$
$\displaystyle=-G^{\prime}(0)\widetilde{\eta}(\overline{\eta}|D|\psi)-|D|(\overline{\eta}B^{\prime}(0)\widetilde{\eta}\psi)+\partial_{x}\\{\overline{\eta}|D|\psi\partial_{x}\widetilde{\eta}\\}$
(B.8)
$\displaystyle=|D|\\{\widetilde{\eta}|D|(\overline{\eta}|D|\psi)\\}+\partial_{x}\\{\widetilde{\eta}\partial_{x}(\overline{\eta}|D|\psi)\\}$
$\displaystyle\quad-|D|\left\\{\overline{\eta}\left[-|D|(\widetilde{\eta}|D|\psi)-\partial_{x}(\widetilde{\eta}\partial_{x}\psi)+\partial_{x}\widetilde{\eta}\partial_{x}\psi\right]\right\\}+\partial_{x}\\{\overline{\eta}|D|\psi\partial_{x}\widetilde{\eta}\\}$
$\displaystyle=|D|\\{\widetilde{\eta}|D|(\overline{\eta}|D|\psi)\\}+\partial_{x}\\{\widetilde{\eta}\partial_{x}(\overline{\eta}|D|\psi)\\}$
$\displaystyle\quad+|D|\left\\{\overline{\eta}|D|(\widetilde{\eta}|D|\psi)\right\\}+|D|\left\\{\overline{\eta}\partial_{x}(\widetilde{\eta}\partial_{x}\psi)\right\\}-|D|\left\\{\overline{\eta}\partial_{x}\widetilde{\eta}\partial_{x}\psi\right\\}+\partial_{x}\\{\overline{\eta}|D|\psi\partial_{x}\widetilde{\eta}\\}.$

Simplifying, we arrive at

$G^{\prime\prime}(0)[\overline{\eta},\widetilde{\eta}]\psi=|D|\\{\widetilde{\eta}|D|(\overline{\eta}|D|\psi)\\}+|D|\left\\{\overline{\eta}|D|(\widetilde{\eta}|D|\psi)\right\\}+|D|\left\\{\overline{\eta}\widetilde{\eta}\partial^{2}_{x}\psi\right\\}+\partial^{2}_{x}\\{\overline{\eta}\widetilde{\eta}|D|\psi\\}.$
(B.9)

###  B.2. Expansion of $p$

We use (B.7) to expand $B^{*}$ up to $\varepsilon^{2}$:

$\displaystyle B^{*}(x):$
$\displaystyle=B(\eta^{*})\psi^{*}=B(0)\psi^{*}+B^{\prime}(0)\eta^{*}\psi^{*}+O(\varepsilon^{2})$
(B.10)
$\displaystyle=|D|\psi^{*}-|D|(\eta^{*}|D|\psi^{*})-\partial_{x}(\eta^{*}\partial_{x}\psi^{*})+\partial_{x}\eta^{*}\partial_{x}\psi^{*}+O(\varepsilon^{2})$
$\displaystyle=|D|(\varepsilon\sin
x+\frac{1}{2}\varepsilon^{2}\sin(2x))-|D|\big{(}(\varepsilon\cos
x)(\varepsilon\sin x)\big{)}-\partial_{x}\big{(}(\varepsilon\cos
x)(\varepsilon\cos x)\big{)}$ $\displaystyle\qquad-(\varepsilon\sin
x)(\varepsilon\cos x)+O(\varepsilon^{3})$ $\displaystyle=(\varepsilon\sin
x+\varepsilon^{2}\sin(2x))-\varepsilon^{2}\big{\\{}\sin(2x)-\sin(2x)+\frac{1}{2}\sin(2x)\big{\\}}+O(\varepsilon^{3})$
$\displaystyle=\varepsilon\sin
x+\frac{1}{2}\varepsilon^{2}\sin(2x)+O(\varepsilon^{3}).$

This implies the expansion for $V^{*}$ up to $\varepsilon^{3}$:

$\displaystyle V^{*}(x)$
$\displaystyle=\partial_{x}\psi^{*}-\partial_{x}\eta^{*}B^{*}$ (B.11)
$\displaystyle=\varepsilon\cos
x+\varepsilon^{2}\cos(2x)+\frac{1}{4}\varepsilon^{3}\big{\\{}3\cos
x\cos(2x)-6\sin x\sin(2x)+\cos x\big{\\}}$
$\displaystyle\quad-\\{-\varepsilon\sin
x-\varepsilon^{2}\sin(2x)\\}\\{\varepsilon\sin
x+\frac{1}{2}\varepsilon^{2}\sin(2x)\\}+O_{\varepsilon}(\varepsilon^{4})$
$\displaystyle=\varepsilon\cos
x+\frac{\varepsilon^{2}}{2}(1+\cos(2x))+\frac{\varepsilon^{3}}{8}(5\cos
x+3\cos(3x))+O(\varepsilon^{4}).$

Regarding $\zeta$, we write

$\zeta=x+\varepsilon\zeta^{1}+\varepsilon^{2}\zeta^{2}+\varepsilon^{3}\zeta^{3}+O(\varepsilon^{4}),\quad\eta^{*}=\varepsilon\eta^{1}+\varepsilon^{2}\eta^{2}+\varepsilon^{3}\eta^{3}+O(\varepsilon^{4}),$

so that by Taylor expansion,

$\displaystyle\eta^{*}(\zeta(x))$
$\displaystyle=\varepsilon\eta^{1}(x)+\varepsilon^{2}(\zeta^{1}\partial_{x}\eta^{1}(x)+\eta^{2}(x))$
(B.12)
$\displaystyle\quad+\varepsilon^{3}\left\\{\zeta^{2}(x)\partial_{x}\eta^{1}(x)+\frac{1}{2}(\zeta^{1}(x))^{2}\partial^{2}_{x}\eta^{1}(x)+\zeta^{1}(x)\partial_{x}\eta^{2}(x)+\eta^{3}(x)\right\\}+O(\varepsilon^{4}).$

It follows from (2.21) that

$\zeta(x)=X(x,0)=x-\frac{i}{2\pi}\sum_{k\neq
0}e^{ikx}\mathrm{sign}(k)\widehat{\eta^{*}\circ\zeta}(k).$ (B.13)

We equate the coefficients of $\varepsilon^{j}$ on both sides to determine
$\zeta^{j}$. It was already found in [28] that $\zeta^{1}(x)=\sin x$ and
$\zeta^{2}(x)=\sin(2x)$. At the order $\varepsilon^{3}$ we have

$\displaystyle\zeta^{3}(x)=-\frac{i}{2\pi}\sum_{k\neq
0}e^{ikx}\mathrm{sign}(k)\widehat{g}(k),$

where

$\displaystyle g(x)$
$\displaystyle=\zeta^{2}(x)\partial_{x}\eta^{1}(x)+\frac{1}{2}(\zeta^{1}(x))^{2}\partial^{2}_{x}\eta^{1}(x)+\zeta^{1}(x)\partial_{x}\eta^{2}(x)+\eta^{3}(x)=-\cos
x+\frac{3}{2}\cos(3x).$

Direct calculations give $\zeta^{3}(x)=-\sin x+\frac{3}{2}\sin(3x)$ and thus

$\zeta(x)=x+\varepsilon\sin
x+\varepsilon^{2}\sin(2x)+\varepsilon^{3}\big{(}-\sin
x+\frac{3}{2}\sin(3x)\big{)}+O(\varepsilon^{4}).$ (B.14)

Inserting (B.14) back in (B.12) gives

$\eta^{*}(\zeta(x))=\varepsilon\cos
x+\varepsilon^{2}\big{(}\cos(2x)-\frac{1}{2}\big{)}+\varepsilon^{3}\big{(}\frac{3}{2}\cos(3x)-\cos
x\big{)}+O(\varepsilon^{4}).$ (B.15)

Using (B.12) with $V^{*}$ in place of $\eta^{*}$ we obtain

$\displaystyle V^{*}(\zeta(x))$ $\displaystyle=\varepsilon
V^{1}(x)+\varepsilon^{2}(\zeta^{1}\partial_{x}V^{1}(x)+V^{2}(x))$ (B.16)
$\displaystyle\quad+\varepsilon^{3}\left\\{\zeta^{2}(x)\partial_{x}V^{1}(x)+\frac{1}{2}(\zeta^{1}(x))^{2}\partial^{2}_{x}V^{1}(x)+\zeta^{1}(x)\partial_{x}V^{2}(x)+V^{3}(x)\right\\}+O(\varepsilon^{4})$
$\displaystyle=\varepsilon\cos
x+\varepsilon^{2}\cos(2x)+\varepsilon^{3}\left\\{\sin(2x)(-\sin
x)+\frac{1}{2}\sin^{2}x(-\cos x)+\sin x(-\sin(2x))\right.$
$\displaystyle\quad\left.+\frac{5}{8}\cos
x+\frac{3}{8}\cos(3x)\right\\}+O(\varepsilon^{4})$
$\displaystyle=\varepsilon\cos
x+\varepsilon^{2}\cos(2x)+\varepsilon^{3}\big{(}-\frac{1}{2}\cos
x+\frac{3}{2}\cos(3x)\big{)}+O(\varepsilon^{4}).$

Combining (B.14) and (B.16) yields the expansion for $p$

$p(x)=\frac{c^{*}-V^{*}(\zeta(x))}{\zeta^{\prime}(x)}=1-2\varepsilon\cos
x+\varepsilon^{2}\big{(}\frac{3}{2}-2\cos(2x)\big{)}+\varepsilon^{3}\big{(}3\cos
x-3\cos(3x)\big{)}+O(\varepsilon^{4}).$ (B.17)

###  B.3. Expansion of $q$ and $\frac{1+q}{\zeta^{\prime}}$

Using (B.6) and (B.8) we expand

$\displaystyle G(\eta^{*})\psi^{*}$
$\displaystyle=G(0)\psi^{*}+G^{\prime}(0)\eta^{*}\psi^{*}+\frac{1}{2}G^{\prime\prime}(0)[\eta^{*},\eta^{*}]\psi^{*}+O(\varepsilon^{4})$
(B.18)
$\displaystyle=|D|\psi^{*}-|D|(\eta^{*}|D|\psi^{*})-\partial_{x}(\eta^{*}\partial_{x}\psi^{*})$
$\displaystyle\quad+\frac{1}{2}|D|\left\\{2\eta^{*}|D|(\eta^{*}|D|\psi^{*})+\eta^{*}\eta^{*}\partial^{2}_{x}\psi^{*}\right\\}+\frac{1}{2}\partial^{2}_{x}\\{\eta^{*}\eta^{*}|D|\psi^{*}\\}+O(\varepsilon^{4})$
$\displaystyle=\varepsilon\sin
x+\varepsilon^{2}\sin(2x)+\varepsilon^{3}\big{(}\frac{5}{8}\sin
x+\frac{9}{8}\sin(3x)\big{)}+O(\varepsilon^{4}).$

Consequently,

$B^{*}(x)=\frac{G(\eta^{*})\psi^{*}+\partial_{x}\eta^{*}\partial_{x}\psi^{*}}{1+|\partial_{x}\eta^{*}|^{2}}=\varepsilon\sin
x+\frac{1}{2}\varepsilon^{2}\sin(2x)+\varepsilon^{3}\big{(}\frac{3}{8}\sin(3x)-\frac{1}{8}\sin(x)\big{)}+O(\varepsilon^{4}).$
(B.19)

Then using (B.12) with $\eta^{*}$ replaced by $B^{*}$ and recalling (B.14), we
obtain

$B^{*}(\zeta(x))=\varepsilon\sin
x+\varepsilon^{2}\sin(2x)+\varepsilon^{3}\big{(}\frac{3}{2}\sin(3x)-\frac{1}{2}\sin
x\big{)}+O(\varepsilon^{4}).$ (B.20)

Combining (B.17) and (B.20) yields

$\displaystyle q(x)=-p(x)\partial_{x}(\zeta_{\sharp}B^{*}(x))=-\varepsilon\cos
x+\varepsilon^{2}(1-\cos(2x))+\varepsilon^{3}\big{(}2\cos
x-\frac{3}{2}\cos(3x)\big{)}+O(\varepsilon^{4}).$ (B.21)

Finally, from (B.14) and (B.21), we deduce

$\frac{1+q(x)}{\zeta^{\prime}(x)}=1-2\varepsilon\cos
x+2\varepsilon^{2}(1-\cos(2x))+\varepsilon^{3}\big{(}4\cos
x-3\cos(3x)\big{)}+O(\varepsilon^{4}).$ (B.22)

Acknowledgment. The work of HQN was partially supported by NSF grant
DMS-2205710. We thank Bernard Deconinck and Massimiliano Berti for
enlightening discussions over several years.

## References

  * [1] T. Alazard, N. Burq, C. Zuily On the water-wave equations with surface tension. Duke Math. J. 158(3): 413–499, 2011.
  * [2] T. Alazard, N. Burq, and C. Zuily. On the Cauchy problem for gravity water waves. Invent.Math., 198(1): 71–163, 2014.
  * [3] T.B Benjamin, and J.E. Feir. The disintegration of wave trains on deep water. Part 1. Theory. J. Fluid Mech. 27 (3): 417–430, 1967.
  * [4] M. Berti, A. Maspero and P. Ventura. Full description of Benjamin-Feir instability of Stokes waves in deep water. Inventiones Math. 230, 651-711, 2022.
  * [5] M. Berti, A. Maspero and P. Ventura. On the analyticity of the Dirichlet-Neumann operator and Stokes waves. arxiv.org 2201.04675, 2022.
  * [6] M. Berti, A. Maspero and P. Ventura. Benjamin-Feir instability of Stokes waves in finite depth. arxiv.org 2204.00809, 2022.
  * [7] M. Berti, A. Maspero and P. Ventura. Stokes waves at the critical depth are modulationally unstable. arxiv.org 2306.13513, 2023.
  * [8] F. Boyer, P. Fabrie. Mathematical tools for the study of the incompressible Navier-Stokes equations and related models. Applied Mathematical Sciences, 183. Springer, New York, 2013. xiv+525 pp.
  * [9] T. J. Bridges, Transverse instability of solitary-wave states of the water wave problem, J. Fluid Mech. 439, 255-278, 2001.
  * [10] T.J. Bridges and A. Mielke. A proof of the Benjamin-Feir instability. Arch. Rational Mech. Anal. 133 no. 2, 145–198, 1995.
  * [11] P. J. Bryant. Oblique instability of periodic waves in shallow water, J. Fluid Mech. 86, 783-792, 1978.
  * [12] G. Chen and Q. Su. Nonlinear modulational instability of the Stokes waves in 2D full water waves. arXiv:2012.15071, 2020.
  * [13] W. Craig and C. Sulem. Numerical simulation of gravity waves. J. Comput. Phys. 108 no. 1, 73–83, 1993.
  * [14] R. Creedon, B. Deconinck and O. Trichtchenko. High-frequency instabilities of Stokes waves, J. Fluid Mech. 937, A24, 2022.
  * [15] R. Creedon and B. Deconinck. A high-order asymptotic analysis of the Benjamin-Feir instability spectrum in arbitrary depth, J. Fluid Mech. 956, A29, 2023.
  * [16] B. Deconinck and K. Oliveras. The instability of periodic surface gravity waves. J. Fluid Mech. vol. 675, 141–167, 2011.
  * [17] B. Deconinck and K. Oliveras. The instabilities of periodic traveling water waves with respect to transverse perturbation. Nonlinear Wave Equ. 635, 131, 2015.
  * [18] M. Haragus,T. Truong and E. Wahlén. Transverse dynamics of two-dimensional traveling periodic gravity-capillary water waves. Water waves, 5, 65-99, 2023.
  * [19] V.M. Hur and Z. Yang. Unstable Stokes waves. Arch. Rational Mech. Anal. 247 (2023), no. 4, Paper No. 62, 59 pp.
  * [20] T. Kato. Perturbation theory for linear operators. Die Grundlehren der mathematischen Wissenschaften, Band 132 Springer-Verlag New York, Inc., New York, 1966.
  * [21] G. Keady and J. Norbury. On the existence theory for irrotational water waves. Math. Proc. Cambridge Phil. Soc. 83, 137-157, 1978.
  * [22] D. Lannes.  Well-posedness of the water waves equations. J. Amer. Math. Soc., 18(3):605–654 (electronic), 2005.
  * [23] T. Levi-Civita. Détermination rigoureuse des ondes permanentes d’ampleur finie. Math. Ann., 93: 264–314, 1925.
  * [24] J. W. McLean. Instabilities of finite-amplitude water waves, J. Fluid Mech. 114, 315-330, 1982.
  * [25] J. W. McLean. Instabilities of finite-amplitude gravity waves on water of infinite depth, J. Fluid Mech. 114, 331-341, 1982.
  * [26] J. W. McLean, Y. C. Ma, and D. U. Martin, P. G Saffman, H. C. Yuen. Three-Dimensional Instability of Finite-Amplitude Water Waves. Phys. Rev. Lett, 46 (13), 817–821, 1981.
  * [27] A.I. Nekrasov. On steady waves. Izv. Ivanovo-Voznesensk. Politekhn. In-ta 3, 1921.
  * [28] H. Q. Nguyen and W. Strauss. Proof of modulational instability of Stokes waves in deep water. Comm. Pure Appl. Math. 76 (2023), no. 5, 1035–1084.
  * [29] H. Q. Nguyen. Large traveling capillary-gravity waves for Darcy flow. Preprint (2023), arXiv:2311.01299.
  * [30] R. L. Pego, and S.-M. Sun. On the transverse linear instability of solitary water waves with large surface tension. Proc, R. Soc. Edinb. 134, 733-752, 2004.
  * [31] F. Rousset and N. Tzvetkov. Transverse instability of the line solitary water-waves. Invent. Math. 184: 257–388, 2011.
  * [32] G.G. Stokes. On the theory of oscillatory waves. Transactions of the Cambridge Philosophical Society, 8: 441–455, 1847.
  * [33] D. J. Struik. Détermination rigoureuse des ondes irrotationnelles périodiques dans un canal à profondeur finie. Math. Ann. 95: 595–634, 1926.
  * [34] V.E. Zakharov. Stability of periodic waves of finite amplitude on the surface of a deep fluid. Journal of Applied Mechanics and Technical Physics 9(2):190–194, 1968.