# The overfullness of graphs with small minimum degree and large maximum
degree

Yan Cao
Department of Mathematics,
West Virginia University, Morgantown, WV 26506
<EMAIL_ADDRESS>Guantao Chen
Department of Mathematics and Statistics,
Georgia State University, Atlanta, GA 30302
<EMAIL_ADDRESS>This work was supported in part by NSF grant DMS-1855716.
Guangming Jing
Department of Mathematics,
Augusta University, Augusta, GA 30912
<EMAIL_ADDRESS>This work was supported in part by NSF grant DMS-2001130.
Songling Shan
Department of Mathematics,
Illinois State Univeristy, Normal, IL 61790
<EMAIL_ADDRESS>
###### Abstract

Given a simple graph $G$, denote by $\Delta(G)$, $\delta(G)$, and
$\chi^{\prime}(G)$ the maximum degree, the minimum degree, and the chromatic
index of $G$, respectively. We say $G$ is _$\Delta$ -critical_ if
$\chi^{\prime}(G)=\Delta(G)+1$ and $\chi^{\prime}(H)\leq\Delta(G)$ for every
proper subgraph $H$ of $G$; and $G$ is _overfull_ if
$|E(G)|>\Delta\lfloor|V(G)|/2\rfloor$. Since a maximum matching in $G$ can
have size at most $\lfloor|V(G)|/2\rfloor$, it follows that
$\chi^{\prime}(G)=\Delta(G)+1$ if $G$ is overfull. Conversely, let $G$ be a
$\Delta$-critical graph. The well known overfull conjecture of Chetwynd and
Hilton asserts that $G$ is overfull provided $\Delta(G)>|V(G)|/3$. In this
paper, we show that any $\Delta$-critical graph $G$ is overfull if
$\Delta(G)-7\delta(G)/4\geq(3|V(G)|-17)/4$.

MSC (2010): Primary 05C15
Keywords: Overfull conjecture, Overfull graph, Kierstead path

##  1 Introduction

We will mainly use the notation from the book [14]. Graphs in this paper are
simple. The vertex set and the edge set of a graph $G$ are denoted by $V(G)$
and $E(G)$, respectively. We denote by $n(G)$, $\Delta(G)$ and $\delta(G)$ the
order, maximum degree and minimum degree of $G$, respectively. When $G$ there
is no risk of confusion, we simply use $n$, $\Delta$ and $\delta$. For two
integers $p,q$, let $[p,q]=\\{i\in\mathbb{Z}:p\leq i\leq q\\}$.

An edge $k$-coloring or simply a _$k$ -coloring_ of a graph $G$ is a mapping
$\varphi$ from $E(G)$ to the set of integers $[1,k]$, called colors, such that
no two adjacent edges receive the same color with respect to $\varphi$. The
chromatic index of $G$, denoted $\chi^{\prime}(G)$, is defined to be the
smallest integer $k$ so that $G$ has an edge $k$-coloring. We denote by
$\mathcal{C}^{k}(G)$ the set of all edge $k$-colorings of $G$. A graph $G$ is
_$\Delta$ -critical_ if $\chi^{\prime}(G)=\Delta+1$ and
$\chi^{\prime}(H)\leq\Delta$ for every proper subgraph $H$ of $G$. In 1960’s,
Vizing [15] and, independently, Gupta [10] proved that
$\Delta\leq\chi^{\prime}(G)\leq\Delta+1$. This leads to a natural
classification of graphs. Following Fiorini and Wilson [8], we say a graph $G$
is of class 1 if $\chi^{\prime}(G)=\Delta$ and of _class 2_ if
$\chi^{\prime}(G)=\Delta+1$. Holyer [11] showed that it is NP-complete to
determine whether an arbitrary graph is of class 1. Nevertheless, if a graph
$G$ has too many edges in comparing with its maximum degree, i.e.,
$|E(G)|>\Delta\lfloor n/2\rfloor$, then we have to color $E(G)$ using exactly
$\Delta+1$ colors. Such graphs are _overfull_. Although the converse is not
true in general, finding sufficient conditions for a class 2 graph to be
overfull has been the major focus in graph edge chromatic theory.

Applying Edmonds’ matching polytope theorem, Seymour [13] showed that whether
a graph $G$ contains an overfull subgraph of maximum degree $\Delta(G)$ can be
determined in polynomial time. A number of long-standing conjectures listed in
Twenty Pretty Edge Coloring Conjectures in [14] lie in deciding when a
$\Delta$-critical graph is overfull. Chetwynd and Hilton [5, 6], in 1986,
proposed the following conjecture.

######  Conjecture 1.1 (Overfull conjecture).

If $G$ is a class 2 graph with $\Delta(G)>\frac{n}{3}$, then $G$ is contains
an overfull subgraph $H$ with $\Delta(H)=\Delta(G)$.

The degree condition that $\Delta>\frac{n}{3}$ in the conjecture above is best
possible, as seen by the graph obtained from the Petersen graph by deleting
one vertex. If the overfull conjecture is true, then the NP-complete problem
of determining the chromatic index becomes polynomial-time solvable for graphs
$G$ with $\Delta>\frac{n}{3}$. Furthermore, the overfull conjecture implies
several other conjectures in edge colorings such as the 1-factorization
conjecture. Despite its importance, very little is known about its truth. It
was confirmed only for graphs with $\Delta\geq n-3$ by Chetwynd and Hilton [6]
in 1989. By restricting the minimum degree, Plantholt [12] in 2004 showed that
the overfull conjecture is affirmative for graphs $G$ with even order $n$ and
minimum degree $\delta\geq\sqrt{7}n/3\approx 0.8819n$. The 1-factorization
conjecture is a special case of the overfull conjecture (when $G$ is regular
with $\Delta\geq n/2$), which in 2013 was confirmed for large $n$ by Csaba,
Kühn, Lo, Osthus, Treglown [7]. The overfull conjecture is still wide open in
general, and it seems extremely difficult even for graphs $G$ with $\Delta\geq
n-4$.

Since every class 2 graph of maximum degree $\Delta$ contains a
$\Delta$-critical subgraph, the overfull conjecture is equivalent to saying
that every $\Delta$-critical graph with $\Delta(G)>\frac{n}{3}$ is overfull.
In this paper, we prove the following result and hope to apply it to verify
the overfull conjecture for graphs with $\Delta\geq(1-\varepsilon)n$ for a
small positive real number $\varepsilon>0$.

######  Theorem 1.2.

Let $G$ be a $\Delta$-critical graph of order $n$. If
$\Delta(G)-\frac{7\delta(G)}{4}\geq\frac{3n-17}{4}$, then $G$ is overfull.

######  Corollary 1.3.

Let $0<\varepsilon<1/7$ be any given real number and $G$ be a
$\Delta$-critical graph of order $n$. Then $G$ is overfull provided that
$\delta(G)\leq\varepsilon n$ and $\Delta\geq\frac{3n-17+7\varepsilon n}{4}$.

The remainder of this paper is organized as follows. In next section, we
introduce some preliminaries on edge colorings such as Vizing fans and
Kierstead paths. In Section 3, we prove Theorem 1.2. In the last section, we
prove one of the main lemmas.

##  2 Preliminaries

In this section, we introduce the fundamental tools such as multifans and
Kierstead paths in edge colorings, and list some new developments built on
these tools. Let $G$ be a graph and $e\in E(G)$. Denote by $G-e$ the graph
obtained from $G$ by deleting the edge $e$. A vertex is called a _$k$ -vertex_
if its degree is $k$; and a neighbor of a vertex $v$ is a _$k$ -neighbor_ if
it is a $k$-vertex in $G$.

An edge $e\in E(G)$ is a _critical edge_ of $G$ if
$\chi^{\prime}(G-e)<\chi^{\prime}(G)$. It is not hard to see that a connected
graph is $\Delta$-critical if and only if every of its edge is critical.
Critical graphs are useful since they have much more graph structural
properties than general class 2 graphs do. For example, Vizing’s Adjacency
Lemma (VAL) from 1965 [15] is a useful tool in counting the number of
$\Delta$-neighbors of a vertex.

######  Lemma 2.1 (VAL).

Let $G$ be a class 2 graph. If $xy$ is a critical edge of $G$, then $x$ has at
least $\Delta-d_{G}(y)+1$ $\Delta$-neighbors from $V(G)\setminus\\{y\\}$.

Let $G$ be a graph, $e\in E(G)$ and $\varphi\in\mathcal{C}^{k}(G-e)$ for some
integer $k\geq 0$. For any $v\in V(G)$, the set of colors _present_ at $v$ is
$\varphi(v)=\\{\varphi(f)\,:\,\text{$f$ is incident to $v$}\\}$, and the set
of colors _missing_ at $v$ is
$\overline{\varphi}(v)=[1,k]\setminus\varphi(v)$. If
$|\overline{\varphi}(v)|=1$, we will also use $\overline{\varphi}(v)$ to
denote the color that is missing at $x$. For a vertex set $X\subseteq V(G)$,
define $\overline{\varphi}(X)=\bigcup_{v\in X}\overline{\varphi}(v).$ The set
$X$ is called _elementary_ with respect to $\varphi$ or simply _$\varphi$
-elementary_ if $\overline{\varphi}(u)\cap\overline{\varphi}(v)=\emptyset$ for
every two distinct vertices $u,v\in X$. Moreover, we sometimes just say that
$X$ is elementary if the edge coloring is understood. For two distinct colors
$\alpha,\beta\in[1,\Delta]$, the components of the subgraph induced by edges
with colors $\alpha$ or $\beta$ are called $(\alpha,\beta)$-chains. Clearly,
each $(\alpha,\beta)$-chain is either a path or an even cycle. For an
$(\alpha,\beta)$-chain $P$, if it is a path with an endvertex $x$, we also
denote it by $P_{x}(\alpha,\beta,\varphi)$ to stress the endvertex $x$. If we
interchange the colors $\alpha$ and $\beta$ on an $(\alpha,\beta)$-chain $C$
of $G$, we get a new edge $k$-coloring of $G$, which is denoted by
$\varphi/C$. This operation is a _Kempe change_. If $C$ is a path with one
endvertex $x$, we may also refer this Kempe change as “do an
$(\alpha,\beta)$-swap at $x$.”

Let $x,y\in V(G)$. If $x$ and $y$ are contained in a same
$(\alpha,\beta)$-chain of $G$ with respect to $\varphi$, we say $x$ and $y$
are _$(\alpha,\beta)$ -linked_ with respect to $\varphi$. Otherwise, $x$ and
$y$ are _$(\alpha,\beta)$ -unlinked_ with respect to $\varphi$. Without
specifying $\varphi$, when we just say $x$ and $y$ are $(\alpha,\beta)$-linked
or $x$ and $y$ are $(\alpha,\beta)$-unlinked, we mean they are linked or
unlinked with respect to the current edge coloring.

A _multi-fan_ at $x$ with respect to edge $e=xy\in E(G)$ and coloring
$\varphi\in\mathcal{C}^{\Delta}(G-e)$ is a sequence
$F=(x,e_{1},y_{1},\ldots,e_{p},y_{p})$ with $p\geq 1$ consisting of edges
$e_{1},e_{2},\ldots,e_{p}$ and distinct vertices $x,y_{1},y_{2},\ldots,y_{p}$
satisfying the following two conditions:

  * •

$e_{1}=e$ and $e_{i}=xy_{i}$ for $i=1,\ldots,p$,

  * •

for every edge $e_{i}$ with $i\in[2,p]$, there is $j\in[1,i-1]$ such that
$\varphi(e_{i})\in\overline{\varphi}(y_{j})$.

Denote by $V(F)$ the set of vertices contained in $F$.

Notice that multi-fan is slightly more general than Vizing-fan which requires
$j=i-1$ in the second condition. The following lemma shows that the vertex set
of a multi-fan is elementary. The proof can be found in the book [14].

######  Lemma 2.2.

[Stiebitz, Scheide, Toft and Favrholdt [14]] Let $G$ be a class 2 graph with
maximum degree $\Delta$, $e_{1}\in E(G)$,
$\varphi\in\mathcal{C}^{\Delta}(G-e_{1})$, and let
$F=(x,e_{1},y_{1},\ldots,e_{p},y_{p})$ be a multi-fan at $x$ with respect to
$e_{1}$ and $\varphi$. Then the following statements hold:

(a) $\\{x,y_{1},y_{2},\ldots,y_{p}\\}$ is $\varphi$-elementary.

(b) For any $\alpha\in\overline{\varphi}(x)$ and
$\beta\in\overline{\varphi}(y_{i})$ for some $i\in[1,p]$, it holds that
$P_{x}(\alpha,\beta,\varphi)=P_{y_{i}}(\alpha,\beta,\varphi)$.

Let a multifan $F=(x,e_{1},y_{1},\ldots,e_{p},y_{p})$ be at $x$ with respect
to $e_{1}$ and $\varphi$, and $y_{\ell_{1}},\ldots,y_{\ell_{k}}$ be a
subsequence of $y_{1},\ldots,y_{p}$. We call
$y_{\ell_{1}},y_{\ell_{2}},\ldots,y_{\ell_{k}}$ an _$\alpha$_ -sequence with
respect to $\varphi$ and $F$ if the following holds:

$\varphi(xy_{\ell_{1}})=\alpha\in\overline{\varphi}(y_{1}),\quad\varphi(xy_{\ell_{i}})\in\overline{\varphi}(y_{\ell_{i-1}}),\quad
i\in[2,k].$

A vertex in an $\alpha$-sequence is called an _$\alpha$ -inducing vertex_ with
respect to $\varphi$ and $F$, and a missing color at an $\alpha$-inducing
vertex is called an _$\alpha$ -inducing color_. For convenience, $\alpha$
itself is also an $\alpha$-inducing color. We say a color $\beta$ is induced
by $\alpha$ if $\beta$ is $\alpha$-inducing. By Lemma 2.2 (a) and the
definition of multifan, each color in $\overline{\varphi}(V(F))$ is induced by
a unique color in $\overline{\varphi}(y_{1})$. Also if $\alpha_{1},\alpha_{2}$
are two distinct colors in $\overline{\varphi}(y_{1})$, then an
$\alpha_{1}$-sequence is disjoint with an $\alpha_{2}$-sequence. For two
distinct $\alpha$-inducing colors $\beta$ and $\delta$, we write
$\mathit{\delta}\prec\beta$ if there exists an $\alpha$-sequence
$y_{\ell_{1}},y_{\ell_{2}},\ldots,y_{\ell_{k}}$ such that
$\delta\in\overline{\varphi}(y_{\ell_{i}})$,
$\beta\in\overline{\varphi}(s_{\ell_{j}})$ and $i<j$. For convenience,
$\alpha\prec\beta$ for any $\alpha$-inducing color $\beta\not=\alpha$. As a
consequence of Lemma 2.2 (a), we have the following properties for a multifan.
A proof of the result can be found in [2, Lemma 3.2].

######  Lemma 2.3.

Let $G$ be a Class 2 graph and $F=(x,e_{1},y_{1},\ldots,e_{p},y_{p})$ be a
multifan with respect to a critical edge $e_{1}=xy_{1}$ and a coloring
$\varphi\in\mathcal{C}^{\Delta}(G-e_{1})$. For two colors
$\delta\in\overline{\varphi}(y_{i})$ and $\lambda\in\overline{\varphi}(y_{j})$
with $i,j\in[1,p]$ and $i\neq j$, the following statements hold.

  1. (a)

If $\delta$ and $\lambda$ are induced by different colors, then $y_{i}$ and
$y_{j}$ are $(\delta,\lambda)$-linked with respect to $\varphi$.

  2. (b)

If $\delta$ and $\lambda$ are induced by the same color, $\delta\prec\lambda$,
and $y_{i}$ and $y_{j}$ are $(\delta,\lambda)$-unlinked with respect to
$\varphi$, then $x\in P_{y_{j}}(\lambda,\delta,\varphi)$.

Let $G$ be a graph, $e=v_{0}v_{1}\in E(G)$, and
$\varphi\in\mathcal{C}^{k}(G-e)$ for some integer $k\geq 0$. A _Kierstead
path_ with respect to $e$ and $\varphi$ is a sequence
$K=(v_{0},v_{0}v_{1},v_{1},v_{1}v_{2},v_{2},\ldots,v_{p-1},v_{p-1}v_{p},v_{p})$
with $p\geq 1$ consisting of distinct vertices $v_{0},v_{1},\ldots,v_{p}$ and
distinct edges $v_{0}v_{1},v_{1}v_{2},\ldots,v_{p-1}v_{p}$ satisfying the
following condition:

  1. (K1)

For every edge $v_{i-1}v_{i}$ with $i\in[2,p]$, there exists $j\in[0,i-2]$
such that $\varphi(v_{i-1}v_{i})\in\overline{\varphi}(v_{j})$.

Clearly, a Kierstead path with at most 3 vertices is a multifan, and so the
set of its vertices is elementary. The following result shows that the set of
the vertices of Kierstead paths with $4$ vertices is “nearly” elementary. (See
Theorem 3.3 from [14].)

######  Lemma 2.4.

Let $G$ be a Class 2 graph, $e=v_{0}v_{1}\in E(G)$ be a critical edge, and
$\varphi\in\mathcal{C}^{\Delta}(G-e)$. If
$K=(v_{0},v_{0}v_{1},v_{1},v_{1}v_{2},v_{2},v_{2}v_{3},v_{3})$ is a Kierstead
path with respect to $e$ and $\varphi$, then the following statements hold.

  1. (a)

If $\min\\{d_{G}(v_{1}),d_{G}(v_{2})\\}<\Delta$, then $V(K)$ is
$\varphi$-elementary.

  2. (b)

$|\overline{\varphi}(v_{3})\cap(\overline{\varphi}(v_{0})\cup\overline{\varphi}(v_{1}))|\leq
1$.

######  Lemma 2.5.

Let $G$ be an $n$-vertex $\Delta$-critical graph and let $a\in V(G)$. If
$d(a)\leq\frac{2\Delta-n+2}{3}$, then for each $v\in V(G)\setminus\\{a\\}$,
either $d(v)\geq\Delta-d(a)+1$ or $d(v)\leq n-\Delta+2d(a)-6$. Furthermore, if
$d(v)\geq\Delta-d(a)+1$, then for any $b\in N(a)$ with $d(b)=\Delta$ and
$\varphi\in\mathcal{C}^{\Delta}(G-ab)$,
$|\overline{\varphi}(v)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\leq
1$.

Proof. Let $k=d(a)$. Assume to the contrary that there exists $v\in
V(G)\setminus\\{a\\}$ such that $n-\Delta+2k-5\leq d(v)\leq\Delta-k$. Let
$b\in N(a)$ with $d(b)=\Delta$ and $\varphi\in\mathcal{C}^{\Delta}(G-ab)$. As
$d(b)=\Delta$, we have $|N(b)\setminus\\{a\\}|=\Delta-1$. Since
$d(v)\leq\Delta-k$, by VAL, $a\not\in N(v)$. As $b,v\not\in N(b)\cap N(v)$ and
$d(v)\geq n-\Delta+2k-5$, it follows that

$\displaystyle|N(v)\cap(N(b)\setminus\\{a\\})|$ $\displaystyle=$
$\displaystyle|((N(v)\cap(N(b)\setminus\\{a\\}))\setminus\\{b,v\\}|$
$\displaystyle=$
$\displaystyle|N(v)|+|N(b)\setminus\\{a\\}|-(n-3)-|N(b)\cap\\{v\\}|-|N(v)\cap\\{b\\}|$
$\displaystyle\geq$ $\displaystyle 2k-3-|N(b)\cap\\{v\\}|-|N(v)\cap\\{b\\}|.$

Note that
$|[1,\Delta]\setminus(\overline{\varphi}(a)\cup\overline{\varphi}(b))|=k-2$.
If $bv\not\in E(G)$, we can find a vertex $u\in
N(v)\cap\big{(}N(b)\setminus\\{a\\}\big{)}$ such that
$\varphi(bu),\varphi(vu)\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$. If
$bv\in E(G)$, then as $d(v)\leq\Delta-k$, by Lemma 2.2 (a), we must have
$\varphi(bv)\not\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$. Thus there
are at most $2(k-3)$ edges between $\\{b,c\\}$ and
$N(v)\cap(N(b)\setminus\\{a\\})$ colored by colors from
$[1,\Delta]\setminus(\overline{\varphi}(a)\cup\overline{\varphi}(b))$. Thus
again we can find a vertex $u\in N(v)\cap\big{(}N(b)\setminus\\{a\\}\big{)}$
such that
$\varphi(bu),\varphi(vu)\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$.
Therefore, $K=(a,ab,b,bu,u,uv,v)$ is a Kierstead path. Since
$d(v)\leq\Delta-k$, $|\overline{\varphi}(v)|\geq k$. This implies that

$|\overline{\varphi}(v)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\geq
2,$

showing a contradiction to Lemma 2.4 (b).

For the second part, since $|N(b)\setminus\\{a\\}|=\Delta-1$ and
$d(v)\geq\Delta-k+1$,

$|N(v)\cap\big{(}N(b)\setminus\\{a\\}\big{)}|\geq 2\Delta-n-k\geq 2k-2,$

as $k=d(a)\leq\frac{2\Delta-n+2}{3}$. The rest of the proof then follows the
same argument as for the first part, and so we omit it. ∎

Lemmas 2.6 to 2.8 below aim to study the “elementary properties” of small
tree-like structures that contain Kierstead paths as substructures.

Let $G$ be a $\Delta$-critical graph, $ab\in E(G)$, and
$\varphi\in\mathcal{C}^{\Delta}(G-ab)$. A fork $H$ with respect to $\varphi$
is a graph with

$V(H)=\\{a,b,u,s_{1},s_{2},t_{1},t_{2}\\}\quad\text{and}\quad
E(H)=\\{ab,bu,us_{1},us_{2},s_{1}t_{1},s_{2}t_{2}\\}$

such that $\varphi(bu)\in\overline{\varphi}(a)$,
$\varphi(us_{1}),\varphi(us_{2})\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$,
and
$\varphi(s_{1}t_{1})\in(\overline{\varphi}(a)\cup\overline{\varphi}(b))\cap\overline{\varphi}(t_{2})$
and
$\varphi(s_{2}t_{2})\in(\overline{\varphi}(a)\cup\overline{\varphi}(b))\cap\overline{\varphi}(t_{1})$.
Fork was defined in [3] and it was shown in [3, Proposition B] that a fork can
not exist in a $\Delta$-critical graph if the degree sum of $a$, $t_{1}$ and
$t_{2}$ is small.

######  Lemma 2.6.

Let $G$ be a $\Delta$-critical graph, $ab\in E(G)$, and
$\\{u,s_{1},s_{2},t_{1},t_{2}\\}\subseteq V(G)$. If $\Delta\geq
d_{G}(a)+d_{G}(t_{1})+d_{G}(t_{2})+1$, then for any
$\varphi\in\mathcal{C}^{\Delta}(G-ab)$, $G$ does not contain a fork on
$\\{a,b,u,s_{1},s_{2},t_{1},t_{2}\\}$ with respect to $\varphi$.

A short-kite $H$ is a graph with

$V(H)=\\{a,b,c,u,x,y\\}\quad\text{and}\quad E(H)=\\{ab,ac,bu,cu,ux,uy\\}.$

The lemma below was proven in [4].

######  Lemma 2.7.

Let $G$ be a class 2 graph, $H\subseteq G$ be a short-kite with
$V(H)=\\{a,b,c,u,x,y\\}$, and let $\varphi\in\mathcal{C}^{\Delta}(G-ab)$.
Suppose

$K=(a,ab,b,bu,u,ux,x)\quad\text{and}\quad K^{*}=(b,ab,a,ac,c,cu,u,uy,y)$

are two Kierstead path with respect to $ab$ and $\varphi$. If
$\overline{\varphi}(x)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))\neq\emptyset$
and
$\overline{\varphi}(y)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))\neq\emptyset$,
then $\max\\{d(x),d(y)\\}=\Delta$.

A kite $H$ is a graph with

$V(H)=\\{a,b,c,u,s_{1},s_{2},t_{1},t_{2}\\}\quad\text{and}\quad
E(H)=\\{ab,ac,bu,cu,us_{1},us_{2},s_{1}t_{1},s_{2}t_{2}\\}.$

######  Lemma 2.8.

Let $G$ be a class 2 graph, $H\subseteq G$ be a kite with
$V(H)=\\{a,b,c,u,s_{1},s_{2},t_{1},t_{2}\\}$, and let
$\varphi\in\mathcal{C}^{\Delta}(G-ab)$. Suppose

$K=(a,ab,b,bu,u,us_{1},s_{1},s_{1}t_{1},t_{1})\quad\text{and}\quad
K^{*}=(b,ab,a,ac,c,cu,u,us_{2},s_{2},s_{2}t_{2},t_{2})$

are two Kierstead paths with respect to $ab$ and $\varphi$. If
$\varphi(s_{1}t_{1})=\varphi(s_{2}t_{2})$, then
$|\overline{\varphi}(t_{1})\cap\overline{\varphi}(t_{2})\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\leq
4$.

The proof of Lemma 2.8 will be given in the last section.

##  3 Proof of Theorem 1.2

Since all vertices not missing a given color $\alpha$ are saturated by the
matching that consists of all edges colored by $\alpha$ in $G$, we have the
Parity Lemma below, which has appeared in many papers, for example, see [9,
Lemma 2.1].

######  Lemma 3.1 (Parity Lemma).

Let $G$ be an $n$-vertex multigraph and $\varphi\in\mathcal{C}^{k}(G)$ for
some integer $k\geq\Delta(G)$. Then for any color $\alpha\in[1,\Delta]$,
$|\\{v\in V(G):\alpha\in\overline{\varphi}(v)\\}|\equiv n\pmod{2}$.

###### Proof of Theorem 1.2.

Since the overfull conjecture is true for $\Delta\geq n-3$ by Chetwynd and
Hilton [6], we may assume that $\Delta\leq n-4$. Thus
$\Delta(G)-\frac{7\delta(G)}{4}\geq\frac{3n-17}{4}$ implies that
$\delta(G)\leq\frac{n+1}{7}$. As $\delta(G)\geq 2$, it follows that $n\geq 13$
and $\Delta(G)\geq\frac{3n-3}{4}$.

Choose $a\in V(G)$ such that $d(a)=\delta(G)=:k$. As
$\Delta\geq\frac{3n-3}{4}$, $\frac{2\Delta-n+2}{3}\geq\frac{n+1}{6}>k$. By
Lemma 2.5, for every $v\in V(G)\setminus\\{a\\}$, we have either

$d(v)\geq\Delta-k+1\quad\text{or}\quad d(v)\leq(n-\Delta)+2k-6.$

Let $b\in N(a)$ with $d(b)=\Delta$ and $\varphi\in\mathcal{C}^{\Delta}(G-ab)$.
We consider two cases below to finish the proof.

Case 1: there exist two distinct vertices $t_{1},t_{2}\in
V(G)\setminus\\{a\\}$ such that $d(t_{1}),d(t_{2})\leq(n-\Delta)+2k-6$.

Let $s_{1}\in N(t_{1})$ and $s_{2}\in N(t_{2})$ be any two distinct vertices
such that
$\varphi(s_{1}t_{1}),\varphi(s_{2}t_{2})\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$.
Such vertices $s_{1},s_{2}$ exists since $d(a)=k=\delta(G)$ and
$|[1,\Delta]\setminus(\overline{\varphi}(a)\cup\overline{\varphi}(b))|=k-2$,
there are at least two edges incident to each of $t_{1}$ and $t_{2}$ colored
by colors from $\overline{\varphi}(a)\cup\overline{\varphi}(b)$. Since $G$ is
$\Delta$-critical, VAL implies that for every $s_{i}\in N(t_{i})$,
$d(s_{i})\geq\Delta+2-(n-\Delta+2k-6)>n-\Delta+2k-6$, where the last
inequality follows as $\Delta-\frac{7k}{4}\geq\frac{3n-17}{4}$ and $n\geq 13$.

By Lemma 2.5, $d(s_{i})\geq\Delta-k+1$. In fact we can assume that
$d(s_{i})\geq\Delta-k+2$. Since if $d(s_{i})=\Delta-k+1$, then $t_{i}$ has at
least $k-1$ neighbors of degree $\Delta$ by VAL. Note that
$k-1>k-2=|[1,\Delta]\backslash(\overline{\varphi}(a)\cup\overline{\varphi}(b))|$,
we may choose $s_{i}$ such that
$\varphi(s_{i}t_{i})\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$ with
$d(s_{i})=\Delta\geq\Delta-k+2$. Thus we assume that $d(s_{i})\geq\Delta-k+2$.
Let $c\in N(a)$ such that $\varphi(ac)\in\overline{\varphi}(b)$. By VAL,
$d(c)\geq\Delta-k+2$. Thus, since $b,c\not\in N(b)\cap N(c)$ and
$s_{1},s_{2}\not\in N(s_{1})\cap N(s_{2})$,

$\displaystyle|N(b)\cap N(c)\cap N(s_{1})\cap N(s_{2})|$ $\displaystyle=$
$\displaystyle|(N(b)\cap N(c)\cap N(s_{1})\cap
N(s_{2}))\backslash\\{b,c,s_{1},s_{2}\\}|$ $\displaystyle\geq$
$\displaystyle|N(s_{1})\cap N(s_{2})|-|N(s_{1})\cap N(s_{2})\cap\\{b,c\\}|$
$\displaystyle+|N(b)\cap N(c)|-|N(b)\cap N(c)\cap\\{s_{1},s_{2}\\}|-(n-4)$
$\displaystyle\geq$ $\displaystyle(2\Delta-n-2k+4)-|N(s_{1})\cap
N(s_{2})\cap\\{b,c\\}|$ $\displaystyle+(2\Delta-n-k+2)-|N(b)\cap
N(c)\cap\\{s_{1},s_{2}\\}|-n+4$ $\displaystyle=$ $\displaystyle
4\Delta-3n-3k+10-|N(s_{1})\cap N(s_{2})\cap\\{b,c\\}|-|N(b)\cap
N(c)\cap\\{s_{1},s_{2}\\}|$ $\displaystyle\geq$
$\displaystyle(k-2-|N(s_{1})\cap\\{b,c\\}|)+(k-2-|N(s_{2})\cap\\{b,c\\}|)+$
$\displaystyle(k-2-|N(b)\cap\\{s_{1},s_{2}\\}|)+(k-2-|N(c)\cap\\{s_{1},s_{2}\\}|)+1,$

as $\Delta\geq 3n/4+(7k-17)/4$. Note that
$|(\overline{\varphi}(a)\cup\overline{\varphi}(b))\cap\overline{\varphi}(t_{i})|\geq
2$ under any $\Delta$-coloring of $G-ab$ since
$d(t_{i})\leq(n-\Delta)+2k-6\leq\Delta-k$. Therefore if $s_{i}b\in E(G)$, then
$\varphi(s_{i}b)\notin\overline{\varphi}(a)\cup\overline{\varphi}(b)$ by Lemma
2.4 (b). By considering the coloring $\varphi^{\prime}$ obtained from
$\varphi$ by coloring $ab$ with $\varphi(ac)$ and uncoloring $ac$, we also
have that if $s_{i}c\in E(G)$, then
$\varphi(s_{i}c)\notin\overline{\varphi}(a)\cup\overline{\varphi}(b)$. Since
$|[1,\Delta]\setminus(\overline{\varphi}(a)\cup\overline{\varphi}(b))|=k-2$,
(1) implies that there exists $u\in N(b)\cap N(c)\cap N(s_{1})\cap N(s_{2})$
such that
$\varphi(ub),\varphi(uc),\varphi(us_{1}),\varphi(us_{2})\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$.
As both $\\{a,b,t_{i}\\}$ and $\\{b,a,s_{i},t_{i}\\}$ are not elementary, it
follows that $u\notin\\{a,t_{1},t_{2}\\}$ by Lemma 2.2 and Lemma 2.4. Thus $H$
with $V(H)=\\{a,b,c,u,s_{1},s_{2},t_{1},t_{2}\\}$ is a kite, and both

$K=(a,ab,b,bu,u,us_{1},s_{1},s_{1}t_{1},t_{1})\quad\text{and}\quad
K^{*}=(b,ab,a,ac,c,cu,u,us_{2},s_{2},s_{2}t_{2},t_{2})$

are Kierstead paths with respect to $ab$ and $\varphi$.

If there exist $s_{1}\in N(t_{1})$ and $s_{2}\in N(t_{2})$ such that
$\varphi(s_{1}t_{1}),\varphi(s_{2}t_{2})\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$
and $\varphi(s_{1}t_{1})=\varphi(s_{2}t_{2})$, then let
$\Gamma=\overline{\varphi}(t_{1})\cap\overline{\varphi}(t_{2})$. Since
$|[1,\Delta]\setminus(\overline{\varphi}(a)\cup\overline{\varphi}(b))|=k-2$,
$|\Gamma\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\geq|\Gamma|-k+2$.
By the assumption of this case,
$|\Gamma|\geq\Delta-2(n-\Delta+2k-6)=3\Delta-2n-4k+12$. As
$\Delta\geq\frac{3n+7k-17}{4}$, $n\geq 13$ and $k\geq 2$, we get

$|\Gamma\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\geq|\Gamma|-k+2\geq
3\Delta-2n-5k+14\geq\frac{n+k+5}{4}\geq 5>4,$

contradicting Lemma 2.8.

Thus for any $s_{1}\in N(t_{1})$ and $s_{2}\in N(t_{2})$ such that
$\varphi(s_{1}t_{1}),\varphi(s_{2}t_{2})\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$,
it follows that $\varphi(s_{1}t_{1})\neq\varphi(s_{2}t_{2})$. Thus
$\varphi(s_{1}t_{1})\in\overline{\varphi}(t_{2})$ and
$\varphi(s_{2}t_{2})\in\overline{\varphi}(t_{1})$. Hence $H^{*}$ with
$V(H^{*})=\\{a,b,u,s_{1},s_{2},t_{1},t_{2}\\}$ is a fork. However,
$d(a)+d(t_{1})+d(t_{2})\leq k+2(n-\Delta+2k-6)=2n-2\Delta+5k-12<\Delta$, as
$n\geq 13$ and $\Delta\geq 3n/4+(7k-17)/4$, contradicting Lemma 2.6.

Case 2: there exists at most one vertex $t\in V(G)\setminus\\{a\\}$ such that
$d(t)\leq(n-\Delta)+2k-6$.

Assume that $G$ is not overfull. We show that we can always find two distinct
vertices $x,y\in V(G)\setminus\\{a\\}$ with

$\Delta-k+1\leq
d(x),d(y)<\Delta,\quad\overline{\varphi}(x)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))\neq\emptyset,\quad\text{and}\quad\overline{\varphi}(y)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))\neq\emptyset.\quad(*)$

Then we will apply Lemma 2.7 to reach a contradiction. To see this, let $c\in
N(a)$ such that $\varphi(ac)\in\overline{\varphi}(b)$. By VAL,
$d(c)\geq\Delta-k+2$. As $d(x),d(y)\geq\Delta-k+1$, by exactly the same
argument as in (3), we can find $u\in N(b)\cap N(c)\cap N(x)\cap N(y)$ such
that $u\not\in\\{a,x,y\\}$ and
$\varphi(ub),\varphi(uc),\varphi(ux),\varphi(uy)\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$.
Then $H$ with $V(H)=\\{a,b,c,u,x,y\\}$ is a short-kite, and both

$K=(a,ab,b,bu,u,ux,x)\quad\text{and}\quad K^{*}=(b,ab,a,ac,c,cu,u,uy,y)$

are Kierstead paths with respect to $ab$ and $\varphi$. As
$\max\\{d(x),d(y)\\}<\Delta$, we achieve a contradiction to Lemma 2.7. Thus we
only show the existence of the vertices $x$ and $y$ below.

Assume first that $n$ is odd. As $G$ is not overfull, some color in
$[1,\Delta]$ is missed at at least three distinct vertices of $G$ by the
Parity Lemma. If there exists exactly one vertex $t\in V(G)\setminus\\{a\\}$
such that $d(t)\leq(n-\Delta)+2k-6$, then each color in
$\overline{\varphi}(t)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))$ is
missed at another vertex from $V(G)\setminus\\{a,b,t\\}$. As
$|\overline{\varphi}(t)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\geq
2\Delta-n-2k+6-(k-2)=2\Delta-n-3k+8>k$, and $d(v)\geq\Delta-k+1$ for every
$v\in V(G)\setminus\\{a,b,t\\}$, we can find $x,y\in V(G)\setminus\\{a\\}$
with the desired property as in $(*)$. Thus for every vertex $v\in
V(G)\setminus\\{a,b\\}$, $d(v)\geq\Delta-k+1$. Let $\delta\in[1,\Delta]$ such
that $\delta$ is missing at at least three vertices, say $u,v,w$, from $V(G)$.
If $\delta\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$, as
$\overline{\varphi}(a)\cup\overline{\varphi}(b)$ is $\varphi$-elementary, then
letting $x,y\in\\{u,v,w\\}\setminus\\{a,b\\}$ will give us a desired choice.
So we assume $\delta\not\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$.
Let $\alpha\in\overline{\varphi}(a)\cup\overline{\varphi}(b)$, say, w.l.g.,
that $\alpha\in\overline{\varphi}(a)$. As at most one of $u,v,w$, say $w$ is
$(\alpha,\delta)$-linked with $a$, we do an $(\alpha,\delta)$-swap at the
other two vertices $u$ and $v$. Call the new coloring still $\varphi$, now $u$
and $v$ can play the role of $x$ and $y$.

Assume now that $n$ is even. As $G$ is not overfull, each color in
$[1,\Delta]$ is missing at an even number of vertices of $G$ by the Parity
Lemma. In particular, we have fact (a): each color in
$\overline{\varphi}(a)\cup\overline{\varphi}(b)$ is missing at a vertex from
$V(G)\setminus\\{a,b\\}$. By the second part of Lemma 2.5, we have fact (b):
for every $v\in V(G)\setminus\\{a,b\\}$, if $\Delta-k+1\leq d(v)\leq\Delta-1$,
then
$|\overline{\varphi}(v)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\leq
1$. Let $t\in V(G)\setminus\\{a,b\\}$ such that $d(t)$ is smallest among the
degrees of vertices from $V(G)\setminus\\{a,b\\}$. As
$|\overline{\varphi}(a)\cup\overline{\varphi}(b)|=\Delta-k+2$ and
$|\overline{\varphi}(t)|\leq\Delta-k$, there exist at least two distinct
colors
$\alpha,\beta\in(\overline{\varphi}(a)\cup\overline{\varphi}(b))\setminus\overline{\varphi}(t)$.
By the assumption of this case, we know that every vertex from
$V(G)\setminus\\{a,b,t\\}$ has degree at least $\Delta-k+1$. Thus by facts (a)
and (b), we can find $x,y\in V(G)\setminus\\{a,b,t\\}$ such that
$\alpha\in\overline{\varphi}(x)$ and $y\in\overline{\varphi}(y)$. Clearly, $x$
and $y$ satisfy the property in $(*)$. This completes the proof. ∎

##  4 Proof of Lemma 2.8

In this section, we prove Lemma 2.8. We start with some notation. Let $G$ be a
graph and $\varphi\in\mathcal{C}^{k}(G-e)$ for some edge $e\in E(G)$ and some
integer $k\geq 0$. For all the concepts below, when we use them later on, if
we skip $\varphi$, we mean the concept is defined with respect to the current
edge coloring.

Let $x,y\in V(G)$, and $\alpha,\beta,\gamma\in[1,k]$ be three colors. Let $P$
be an $(\alpha,\beta)$-chain of $G$ with respect to $\varphi$ that contains
both $x$ and $y$. If $P$ is a path, denote by
$\mathit{P_{[x,y]}(\alpha,\beta,\varphi)}$ the subchain of $P$ that has
endvertices $x$ and $y$. By _swapping colors_ along
$P_{[x,y]}(\alpha,\beta,\varphi)$, we mean exchanging the two colors $\alpha$
and $\beta$ on the path $P_{[x,y]}(\alpha,\beta,\varphi)$.

Define $P_{x}(\alpha,\beta,\varphi)$ to be an $(\alpha,\beta)$-chain or an
$(\alpha,\beta)$-subchain of $G$ with respect to $\varphi$ that starts at $x$
and ends at a different vertex missing exactly one of $\alpha$ and $\beta$. If
$x$ is an endvertex of the $(\alpha,\beta)$-chain that contains $x$, then
$P_{x}(\alpha,\beta,\varphi)$ is unique. Otherwise, we take one segment of the
whole chain to be $P_{x}(\alpha,\beta,\varphi)$. We will specify the segment
when it is used.

If $u$ is a vertrex on $P_{x}(\alpha,\beta,\varphi)$, we write $\mathit{u\in
P_{x}(\alpha,\beta,\varphi)}$; and if $uv$ is an edge on
$P_{x}(\alpha,\beta,\varphi)$, we write $\mathit{uv\in
P_{x}(\alpha,\beta,\varphi)}$. If $u,v\in P_{x}(\alpha,\beta,\varphi)$ such
that $u$ lies between $x$ and $v$ on the path, then we say that
$P_{x}(\alpha,\beta,\varphi)$ _meets $u$ before $v$_. Suppose the current
color of an edge $uv$ of $G$ is $\alpha$, the notation
$\mathit{uv:\alpha\rightarrow\beta}$ means to recolor the edge $uv$ using the
color $\beta$. Suppose that $\alpha\in\overline{\varphi}(x)$ and
$\beta,\gamma\in\varphi(x)$. An $\mathit{(\alpha,\beta)-(\beta,\gamma)}$ _swap
at $x$_ consists of two operations: first swaps colors on
$P_{x}(\alpha,\beta,\varphi)$ to get an edge $k$-coloring $\varphi^{\prime}$,
and then swaps colors on $P_{x}(\beta,\gamma,\varphi^{\prime})$. By
convention, an $(\alpha,\alpha)$-swap at $x$ does nothing at $x$.

Let $\alpha,\beta,\gamma,\tau,\eta\in[1,k]$. We will use a matrix with two
rows to denote a sequence of operations taken on $\varphi$. Each entry in the
first row represents a path or a sequence of vertices. Each entry in the
second row, indicates the action taken on the object above this entry. We
require the operations to be taken to follow the “left to right” order as they
appear in the matrix. For example, the matrix below indicates three sequential
operations taken on the graph based on the coloring from the previous step:

$\begin{bmatrix}P_{[a,b]}(\alpha,\beta)&rs&ab\\\
\alpha/\beta&\gamma\rightarrow\tau&\eta\end{bmatrix}.$

  1. Step 1

Swap colors on the $(\alpha,\beta)$-subchain
$P_{[a,b]}(\alpha,\beta,\varphi)$.

  2. Step 2

Do $rs:\gamma\rightarrow\tau$.

  3. Step 3

Color the edge $ab$ using color $\eta$.

We will need the following result on Kierstead paths with 5 vertices in
proving Lemma 2.8. General properties on Kierstead paths with 5 vertices was
proved by the first author of this paper [1]. Here we stress only one of the
cases.

######  Lemma 4.1.

Let $G$ be a class 2 graph, $ab\in E(G)$ be a critical edge,
$\varphi\in\mathcal{C}^{\Delta}(G-ab)$, and $K=(a,ab,b,bu,u,us,s,st,t)$ be a
Kierstead path with respect to $ab$ and $\varphi$. If
$|\overline{\varphi}(t)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\geq
3$, then the following holds:

  1. (a)

There exists $\varphi^{*}\in\mathcal{C}^{\Delta}(G-ab)$ satisfying the
following properties:

    1. (i)

$\varphi^{*}(bu)\in\overline{\varphi}^{*}(a)\cap\overline{\varphi}^{*}(t)$,

    2. (ii)

$\varphi^{*}(us)\in\overline{\varphi}^{*}(b)\cap\overline{\varphi}^{*}(t)$,
and

    3. (iii)

$\varphi^{*}(st)\in\overline{\varphi}^{*}(a)$.

  2. (b)

$d_{G}(b)=d_{G}(u)=\Delta$.

Figure 1 shows a Kierstead path with the properties described in (a).

$a$$b$$u$$s$$t$$\alpha$ $\beta$ $\gamma$
$\beta$$\gamma$$\alpha$$\beta$$\alpha$ Figure 1: Colors on a Kierstead path of
5 vertices

Proof. We prove (a). By Lemma 2.2, for every
$\varphi^{\prime}\in\mathcal{C}^{\Delta}(G-ab)$, $\\{a,b\\}$ is
$\varphi^{\prime}$-elementary and for every
$i\in\overline{\varphi}^{\prime}(a)$ and $j\in\overline{\varphi}^{\prime}(b)$,
$a$ and $b$ are $(i,j)$-linked with respect to $\varphi^{\prime}$.

Let
$\Gamma=\overline{\varphi}(t)\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))$,
and $\alpha,\beta\in\Gamma$ be distinct. If
$\alpha,\beta\in\overline{\varphi}(a)$, then we let
$\lambda\in\overline{\varphi}(b)$, and do a $(\beta,\lambda)$-swap at $b$. If
$\alpha,\beta\in\overline{\varphi}(b)$, then we let
$\lambda\in\overline{\varphi}(a)$, and do a $(\beta,\lambda)$-swap at $a$.
Therefore, we may assume that

$\alpha\in\overline{\varphi}(a)\quad\text{and}\quad\beta\in\overline{\varphi}(b).$

If $\varphi(bu)=\delta\neq\alpha$, which implies
$\delta\in\overline{\varphi}(a)$, then we do a $(\beta,\delta)$-swap and then
an $(\alpha,\beta)$-swap at $t$, and rename the color $\delta$ as $\alpha$ and
vice versa. Thus we may assume

$\varphi(bu)=\alpha.$

Assume first that $\varphi(us)\in\overline{\varphi}(b)$ and let
$\varphi(us)=\tau$. If $us\not\in P_{t}(\beta,\tau)$, we do a
$(\beta,\tau)$-swap at $t$ and still call the resulting coloring by $\varphi$,
we see that $\tau\in\overline{\varphi}(b)\cap\overline{\varphi}(t)$. By
exchanging the colors $\beta$ and $\tau$, we have $\varphi(us)=\beta$. If
$us\in P_{t}(\beta,\tau)$, we do a $(\beta,\tau)$-swap at $t$ and further do
an $(\alpha,\beta)$-swap and then an $(\alpha,\tau)$-swap at $t$, which gives
a new coloring, still call it $\varphi$, such that $\varphi(us)=\beta$. Let
$\varphi(st)=\gamma$. Since $\alpha,\beta\in\overline{\varphi}(t)$,
$\gamma\neq\alpha,\beta$. If $\gamma\in\overline{\varphi}(a)$, we are done. So
we assume $\gamma\in\overline{\varphi}(b)\cup\overline{\varphi}(u)$. We color
$ab$ by $\alpha$ and uncolor $bu$. Denote this resulting coloring by
$\varphi^{\prime}$. Then $K^{\prime}=(b,bu,u,us,s,st,t)$ is a Kierstead path
with respect to $bu$ and $\varphi^{\prime}$. However,
$\alpha,\beta\in\overline{\varphi}^{\prime}(t)\cap(\overline{\varphi}^{\prime}(b)\cup\overline{\varphi}^{\prime}(u))$,
showing a contradiction to Lemma 2.4 (b).

Thus we let $\varphi(us)=\delta\in\overline{\varphi}(a)$. Then
$\delta\neq\beta$ by Lemma 2.2 (a). Let $\varphi(st)=\gamma$. Clearly,
$\gamma\neq\alpha,\beta,\delta$. We have either
$\gamma\in\overline{\varphi}(a)$ or
$\gamma\in\overline{\varphi}(b)\cup\overline{\varphi}(u)$. We consider three
cases below.

Case 1. $\gamma\in\overline{\varphi}(b)$.

If $u\in P_{a}(\beta,\delta)=P_{b}(\beta,\delta)$, we do a
$(\beta,\delta)$-swap at $t$. Since $a$ and $b$ are $(\delta,\gamma)$-linked
and $u\in P_{t}(\delta,\gamma)$, we do a $(\delta,\gamma)$-swap at $a$. By
renaming colors, this gives a desired coloring $\varphi^{*}$.

If $u\not\in P_{a}(\beta,\delta)=P_{b}(\beta,\delta)$, we first do a
$(\beta,\delta)$-swap at $a$ and then a $(\beta,\gamma)$-swap at $a$. Again
this gives a desired coloring $\varphi^{*}$ after renaming colors.

Case 2. $\gamma\in\overline{\varphi}(u)$.

If $\delta\in\Gamma$, since $b$ and $u$ are $(\beta,\gamma)$-linked by Lemma
2.2 (b), we do $(\beta,\gamma)$-swap at $t$. Now $u\in P_{t}(\delta,\beta)$,
we do a $(\beta,\delta)$-swap at $a$. This gives a desired coloring
$\varphi^{*}$. Thus we assume $\delta\not\in\Gamma$. Since $b$ and $u$ are
$(\beta,\gamma)$-linked by Lemma 2.2 (b), and $a$ and $u$ are
$(\delta,\gamma)$-linked by Lemma 2.3 (a), we do
$(\beta,\gamma)-(\gamma,\delta)$-swaps at $t$. Finally, since $u\in
P_{t}(\beta,\delta)$, we do a $(\beta,\delta)$-swap at $a$. This gives a
desired coloring $\varphi^{*}$.

Case 3. $\gamma\in\overline{\varphi}(a)$.

If $\delta\in\Gamma$, we do a $(\beta,\gamma)$-swap at $t$ and then a
$(\beta,\delta)$-swap at $a$ to get a desired coloring $\varphi^{*}$. Thus we
assume $\delta\not\in\Gamma$. Let $\tau\in\Gamma\setminus\\{\alpha,\beta\\}$.
If $\tau\in\overline{\varphi}(u)$, since $a$ and $u$ are
$(\tau,\delta)$-linked by Lemma 2.3 (a), we do a $(\tau,\delta)$-swap at $t$.
This gives back to the previous case that $\delta\in\Gamma$. Next we assume
$\tau\in\overline{\varphi}(b)$. It is clear that $u\in
P_{a}(\tau,\delta)=P_{b}(\tau,\delta)$, as otherwise, a $(\tau,\delta)$-swap
at $a$ gives a desired coloring. Thus we do a $(\tau,\delta)$-swap at $t$,
giving back to the previous case that $\delta\in\Gamma$.

Now we assume $\tau\in\overline{\varphi}(a)$. If $u\not\in
P_{a}(\beta,\delta)$, we do a $(\beta,\delta)$-swap at $a$. Since $a$ and $b$
are $(\alpha,\delta)$-linked and $u\in P_{a}(\alpha,\delta)$, we do an
$(\alpha,\delta)$ swap at $t$. Now since $u\in P_{t}(\gamma,\delta)$, we do a
$(\gamma,\delta)$-swap at $a$, and do $(\beta,\gamma)-(\gamma,\alpha)$-swaps
at $t$. Since $a$ and $b$ are $(\tau,\gamma)$-linked, we do a
$(\tau,\gamma)$-swap at $t$, and then a $(\beta,\gamma)$ -swap at $a$. Now
since $u\in P_{t}(\beta,\delta)$, we do a $(\beta,\delta)$-swap at $a$. This
gives a desired coloring. Thus, we assume $u\in P_{a}(\beta,\delta)$. We do a
$(\beta,\delta)$-swap at $t$, and then a $(\tau,\beta)$-swap at $t$. Next we
do a $(\beta,\gamma)$-swap at $a$ and then a $(\gamma,\delta)$-swap at $a$.
This gives a desired coloring.

For statement (b), let $\varphi^{*}\in\mathcal{C}^{\Delta}(G-ab)$ satisfying
(i)–(iii). Let $\alpha,\gamma\in\overline{\varphi}^{*}(a)$,
$\beta\in\overline{\varphi}^{*}(b)$ with
$\alpha,\beta\in\overline{\varphi}(t)$ such that

$\varphi^{*}(bu)=\alpha,\quad\varphi^{*}(us)=\beta,\quad\text{and}\quad\varphi^{*}(st)=\gamma.$

Let $\tau\in\overline{\varphi}^{*}(t)\setminus\\{\alpha,\beta\\}$. Suppose to
the contrary first that $d_{G}(b)\leq\Delta-1$. Let
$\lambda\in\overline{\varphi}^{*}(b)\setminus\\{\beta\\}$. We do
$(\tau,\lambda)-(\lambda,\gamma)$-swaps at $t$. Now we color $ab$ by $\alpha$
and uncolor $bu$ to get a coloring $\varphi^{\prime}$. Then
$K^{\prime}=(b,bu,u,us,s,st,t)$ is a Kierstead path with respect to $bu$ and
$\varphi^{\prime}$. However,
$\alpha,\beta\in\overline{\varphi}^{\prime}(t)\cap(\overline{\varphi}^{\prime}(b)\cup\overline{\varphi}^{\prime}(u))$,
contradicting Lemma 2.4 (b).

Assume then that $d_{G}(b)=\Delta$ and $d_{G}(u)\leq\Delta-1$. Let
$\lambda\in\overline{\varphi}^{*}(u)$. Since $(a,ab,b,bu,u)$ is a multifan,
$\lambda\not\in\\{\alpha,\beta,\gamma\\}$. Since $u$ and $b$ are
$(\beta,\lambda)$-linked and $u$ and $a$ are $(\gamma,\lambda)$-linked by
Lemma 2.3 (b), we do $(\beta,\lambda)-(\lambda,\gamma)$-swap(s) at $t$. Now we
color $ab$ by $\alpha$ and uncolor $bu$ to get a coloring $\varphi^{\prime}$.
Then $K^{\prime}=(b,bu,u,us,s,st,t)$ is a Kierstead path with respect to $bu$
and $\varphi^{\prime}$. However,
$\alpha\in\overline{\varphi}^{\prime}(t)\cap\overline{\varphi}^{\prime}(u)$,
which contradicts Lemma 2.4 (a) since $d_{G}(u)<\Delta$. ∎

We are now ready to prove Lemma 2.8.

######  Lemma 2.8.

Let $G$ be a class 2 graph, $H\subseteq G$ be a kite with
$V(H)=\\{a,b,c,u,s_{1},s_{2},t_{1},t_{2}\\}$, and let
$\varphi\in\mathcal{C}^{\Delta}(G-ab)$. Suppose

$K=(a,ab,b,bu,u,us_{1},s_{1},s_{1}t_{1},t_{1})\quad\text{and}\quad
K^{*}=(b,ab,a,ac,c,cu,u,us_{2},s_{2},s_{2}t_{2},t_{2})$

are two Kierstead paths with respect to $ab$ and $\varphi$. If
$\varphi(s_{1}t_{1})=\varphi(s_{2}t_{2})$, then
$|\overline{\varphi}(t_{1})\cap\overline{\varphi}(t_{2})\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))|\leq
4$.

Proof. Let
$\Gamma=\overline{\varphi}(t_{1})\cap\overline{\varphi}(t_{2})\cap(\overline{\varphi}(a)\cup\overline{\varphi}(b))$.
Assume to the contrary that $|\Gamma|\geq 5$. By considering $K$ and applying
Lemma 4.1, we conclude that $d_{G}(b)=d_{G}(u)=\Delta$. We show that there
exists $\varphi^{*}\in\mathcal{C}^{\Delta}(G-ab)$ satisfying the following
properties:

  1. (i)

$\varphi^{*}(bu),\varphi^{*}(cu),\varphi^{*}(us_{2})\in\overline{\varphi}^{*}(a)\cap\overline{\varphi}^{*}(t_{1})\cap\varphi^{*}(t_{2})$,

  2. (ii)

$\varphi^{*}(us_{1})\in\overline{\varphi}^{*}(b)\cap\overline{\varphi}^{*}(t_{1})\cap\varphi^{*}(t_{2})$,
and

  3. (iii)

$\varphi^{*}(s_{1}t_{1})=\varphi^{*}(s_{2}t_{2})\in\overline{\varphi}^{*}(a)$.

See Figure 2 for a depiction of the colors described above.

$a$$b$$c$$u$$s_{1}$$s_{2}$$t_{1}$$t_{2}$$\beta$$\tau$$\alpha$ $\beta$ $\gamma$
$\gamma$
$\delta$$\alpha$$\alpha$$\beta$$\beta$$\tau$$\tau$$\delta$$\delta$$\beta$$\gamma$$\alpha$$\tau$$\delta$
Figure 2: Colors on the edges of a kite

Let $\alpha,\beta,\tau,\delta\in\Gamma$ be distinct, and let
$\varphi(s_{1}t_{1})=\varphi(s_{2}t_{2})=\gamma$. We may assume that
$\alpha\in\overline{\varphi}(a)$ and $\beta\in\overline{\varphi}(b)$.
Otherwise, since $d_{G}(b)=\Delta$, we have
$\alpha,\beta\in\overline{\varphi}(a)$. Let $\lambda\in\overline{\varphi}(b)$.
As $a$ and $b$ are $(\beta,\lambda)$-linked, we do a $(\beta,\lambda)$-swap at
$b$. Note that this operation may change some colors of the edges of $K$ and
$K^{*}$, but they are still Kierstead paths with respect to $ab$ and the
current coloring. Note that $\varphi(ac)=\beta$, since
$\overline{\varphi}(b)=\\{\beta\\}$ and $K^{*}$ is a Kierstead path.

Since $d_{G}(b)=d_{G}(u)=\Delta$, and
$\beta\in\overline{\varphi}(b)\cap\overline{\varphi}(t_{1})$, we know that
$\gamma\in\overline{\varphi}(a)$, as $K_{1}$ is a Kierstead path. Next, we may
assume that $\varphi(bu)=\alpha$. If not, let $\varphi(bu)=\alpha^{\prime}$.
Since $a$ and $b$ are $(\alpha,\beta)$-linked, we do an $(\alpha,\beta)$-swap
at $b$. Now $a$ and $b$ are $(\alpha,\alpha^{\prime})$-linked, we do an
$(\alpha,\alpha^{\prime})$-swap at $b$. Finally, we do an
$(\alpha^{\prime},\beta)$-swap at $b$. All these swaps do not change the
colors in $\Gamma$, so now we get the color on $bu$ to be $\alpha$.

We may now assume that $\varphi(cu)=\tau$. If not, let
$\varphi(cu)=\tau^{\prime}$. Then $\tau^{\prime}\in\overline{\varphi}(a)$.
Since $a$ and $b$ are $(\beta,\tau)$-linked, we do a $(\beta,\tau)$-swap at
$b$. Then do $(\tau,\tau^{\prime})-(\tau^{\prime},\beta)$-swaps at $b$.

Finally, we show that we can modify $\varphi$ to get $\varphi^{\prime}$ such
that $\varphi^{\prime}(us_{1})=\beta$ and $\varphi^{\prime}(us_{2})=\delta$.
Let $\lambda\in\Gamma\setminus\\{\alpha,\beta,\tau,\delta\\}$. Assume firstly
that $\varphi(us_{1})=\beta^{\prime}\neq\beta$. Then
$\beta^{\prime}\in\overline{\varphi}(a)$ as
$\overline{\varphi}(b)=\\{\beta\\}$ and $\overline{\varphi}(u)=\emptyset$. If
$\beta^{\prime}\in\Gamma$, we do
$(\beta,\gamma)-(\gamma,\beta^{\prime})$-swaps at $b$. Thus, we assume
$\beta^{\prime}\not\in\Gamma$. If $u\not\in
P_{a}(\beta,\beta^{\prime})=P_{b}(\beta,\beta^{\prime})$, we simply do a
$(\beta,\beta^{\prime})$-swap at $b$. Thus, we assume $u\in
P_{a}(\beta,\beta^{\prime})=P_{b}(\beta,\beta^{\prime})$. We do a
$(\beta,\beta^{\prime})$-swap at both $t_{1}$ and $t_{2}$. Since $a$ and $b$
are $(\beta,\lambda)$-linked, we do a $(\beta,\lambda)$-swap at both $t_{1}$
and $t_{2}$. Now we do $(\beta,\gamma)-(\gamma,\beta^{\prime})$-swaps at $b$.
By switching the role of $\beta$ and $\beta^{\prime}$, we have
$\varphi(us_{1})=\beta$.

Lastly, we show that $\varphi(us_{2})=\delta$. Assume otherwise that
$\varphi(us_{2})=\delta^{\prime}$. By coloring $ab$ with the color $\beta$ and
uncoloring $ac$, we have $d_{G}(c)=\Delta$ by Lemma 4.1. Thus
$\delta^{\prime}\in\overline{\varphi}(a)$. Note that $bu\in
P_{t_{1}}(\alpha,\gamma)$. Otherwise, let
$\varphi^{\prime}=\varphi/P_{t_{1}}(\alpha,\gamma)$. Then
$P_{b}(\alpha,\beta)=bus_{1}t_{1}$, showing a contradiction to the fact that
$a$ and $b$ are $(\alpha,\beta)$-linked with respect to $\varphi^{\prime}$.
Thus, $bu\in P_{t_{1}}(\alpha,\gamma)$. Next, we claim that
$P_{t_{1}}(\alpha,\gamma)$ meets $u$ before $b$. As otherwise, we do the
following operations to get a $\Delta$-coloring of $G$:

$\begin{bmatrix}s_{1}t_{1}&P_{[s_{1},b]}(\alpha,\gamma)&us_{1}&bu&ab\\\
\gamma\rightarrow\beta&\alpha/\gamma&\beta\rightarrow\alpha&\alpha\rightarrow\beta&\gamma\end{bmatrix}.$

This gives a contradiction to the assumption that $G$ is $\Delta$-critical.
Thus, we have that $P_{t_{1}}(\alpha,\gamma)$ meets $u$ before $b$. This
implies that it is not the case that $P_{t_{2}}(\alpha,\gamma)$ meets $u$
before $b$. In turn, this implies that $u\in
P_{a}(\beta,\delta^{\prime})=P_{b}(\beta,\delta^{\prime})$. As otherwise, we
get a $\Delta$-coloring of $G$ by doing a $(\beta,\delta^{\prime})$-swap along
the $(\beta,\delta^{\prime})$-chain containing $u$, and then doing the same
operation as above with $t_{2}$ playing the role of $t_{1}$.

Since $u\in P_{a}(\beta,\delta^{\prime})=P_{b}(\beta,\delta^{\prime})$, we do
a $(\beta,\delta^{\prime})$-swap at both $t_{1}$ and $t_{2}$. As $u\in
P_{a}(\beta,\tau)=P_{b}(\beta,\tau)$, we do a $(\beta,\tau)$-swap at both
$t_{1}$ and $t_{2}$. Since $us_{1}\in P_{t_{1}}(\beta,\gamma)$, we do a
$(\beta,\gamma)$-swap at $b$, then a $(\gamma,\lambda)$-swap at $b$. Since $a$
and $b$ are $(\tau,\lambda)$-linked, we do a $(\tau,\lambda)$-swap at both
$t_{1}$ and $t_{2}$. Now
$(\lambda,\delta)-(\delta,\gamma)-(\gamma,\beta)$-swaps at $b$ give a desired
coloring.

Still, by the same arguments as above, we have that $P_{t_{1}}(\alpha,\gamma)$
meets $u$ before $b$, and $u\in P_{a}(\beta,\delta)=P_{b}(\beta,\delta)$. Let
$P_{u}(\beta,\delta)$ be the $(\beta,\delta)$-chain starting at $u$ not
including the edge $us_{2}$. It is clear that $P_{u}(\beta,\delta)$ ends at
either $a$ or $b$. We may assume that $P_{u}(\beta,\delta)$ ends at $a$.
Otherwise, we color $ab$ by $\beta$, uncolor $ac$, and let $\tau$ play the
role of $\alpha$. Let $P_{u}(\alpha,\gamma)$ be the $(\alpha,\gamma)$-chain
starting at $u$ not including the edge $bu$, which ends at $t_{1}$ by our
earlier argument. We do the following operations to get a $\Delta$-coloring of
$G$:

$\begin{bmatrix}P_{u}(\alpha,\gamma)&bu&P_{u}(\beta,\delta)&us_{2}t_{2}&ab\\\
\alpha/\gamma&\alpha\rightarrow\beta&\beta/\delta&\delta/\gamma&\alpha\end{bmatrix}.$

This gives a contradiction to the assumption that $G$ is $\Delta$-critical.
The proof is now finished. ∎

## References

  * [1] Y. Cao.  Kierstead path of 5 vertices.  A manuscript, 2017.
  * [2] Y. Cao, G. Chen, G. Jing, and S. Shan.  Proof of the Core Conjecture of Hilton and Zhao.  arXiv:2004.00734, 2020.
  * [3] Y. Cao and G. Chen.  On the average degree of edge chromatic critical graphs II.  J. Combin. Theory Ser. B, 145:470–486, 2020.
  * [4] Y. Cao, G. Chen, and S. Shan.  An improvement to the vertex-splitting conjecture.  arXiv:2103.05171, 2021.
  * [5] A. G. Chetwynd and A. J. W. Hilton.  Star multigraphs with three vertices of maximum degree.  Math. Proc. Cambridge Philos. Soc., 100(2):303–317, 1986.
  * [6] A. G. Chetwynd and A. J. W. Hilton.  The edge-chromatic class of graphs with maximum degree at least $|V|-3$.  In Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), volume 41 of Ann. Discrete Math., pages 91–110. North-Holland, Amsterdam, 1989.
  * [7] B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown.  Proof of the 1-factorization and Hamilton decomposition conjectures.  Mem. Amer. Math. Soc., 244(1154):v+164, 2016.
  * [8] S. Fiorini and R. J. Wilson.  Edge-colourings of graphs, Research notes in Maths.  Pitman, London, 1977.
  * [9] S. Grünewald and E. Steffen.  Independent sets and 2-factors in edge-chromatic-critical graphs.  J. Graph Theory, 45(2):113–118, 2004.
  * [10] R. G. Gupta.  Studies in the Theory of Graphs.  PhD thesis, Tata Institute of Fundamental Research, Bombay, 1967.
  * [11] I. Holyer.  The NP-completeness of edge-coloring.  SIAM J. Comput., 10(4):718–720, 1981.
  * [12] M. Plantholt.  Overfull conjecture for graphs with high minimum degree.  J. Graph Theory, 47(2):73–80, 2004.
  * [13] P. D. Seymour.  On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.  Proc. London Math. Soc. (3), 38(3):423–460, 1979.
  * [14] M. Stiebitz, D. Scheide, B. Toft, and L. M. Favrholdt.  Graph edge coloring.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2012.  Vizing’s theorem and Goldberg’s conjecture, With a preface by Stiebitz and Toft.
  * [15] V. G. Vizing.  Critical graphs with given chromatic class.  Diskret. Analiz No., 5:9–17, 1965.


# Semiclassical approach to spin dynamics of a ferromagnetic $S=1$
chain††thanks: Project supported by the National Key R&D Program of China
(Grant No. 2023YFA1406500), and the National Science Foundation of China
(Grant Nos. 12334008 and 12174441)

Chengchen Li 1 Yi Cui 1,2 Weiqiang Yu 1,2 and Rong Yu 1,2
1Department of Physics and Beijing Key Laboratory of Opto-electronic
Functional Materials
and Micro-nano Devices Corresponding author<EMAIL_ADDRESS>Renmin
University of China  Beijing 100872  China
2Key Laboratory of Quantum State Construction and Manipulation (Ministry of
Education)
Renmin University of China  Beijing  100872  China

###### Abstract

Motivated by recent experimental progress in the quasi-one-dimensional quantum
magnet NiNb2O6, we study the spin dynamics of an $S=1$ ferromagnetic
Heisenberg chain with single-ion anisotropy by using a semiclassical molecular
dynamics approach. This system undergoes a quantum phase transition from a
ferromagnetic to a paramagnetic state under a transverse magnetic field, and
the magnetic responses reflecting this transition is well described by our
semiclassical method. We show that at low-temperature the transverse component
of the dynamical structure factor depicts clearly the magnon dispersion, and
the longitudinal component exhibits two continua associated with single- and
two-magnon excitations, respectively. These spin excitation spectra show
interesting temperature dependence as effects of magnon interactions. Our
findings shed light on experimental detection of spin excitations in a large
class of quasi-one-dimensional magnets.

Keywords: One-dimensional ferromagnetism, spin dynamics, magnon excitation,
molecular dynamics

PACS: 75.10.Jm, 75.40.Gb, 75.40.Mg

##  1 Introduction

Quantum fluctuations in quasi-one-dimensional (q1D) quantum spin systems can
give rise to a number of novel quantum phases and exotic emergent phenomena,
including fractionalized excitations, symmetry protected topological order,
and emergent quantum integrability [1, 2, 3, 4, 5, 6, 7, 8, 9]. Many
interesting phenomena are associated with quantum antiferromagnetic (AFM)
systems for the strong quantum fluctuations in these systems: On the one hand,
the AFM order parameter does not commute with the Heisenberg or XXZ
Hamiltonian. On the other hand, frustration effects are more significant in
AFM systems. As for ferromagnetic (FM) systems, many properties have been well
studied. For example, the ground state of a FM Heisenberg model is a simple
product state with all spins aligned in parallel, and the elementary
excitation is a spin wave, or a magnon, which carries a spin quantum number
$S=1$.[10]

Recently, there are numerous experimental and theoretical studies on a q1D FM
quantum magnet CoNb2O6.[11, 12, 13, 14, 15, 16] This compound consists of
effective $S=1/2$ FM chains that are aligned in a frustrated manner (forming a
triangular lattice in the plane perpendicular to the chain direction). Along
each chain, the system is approximately described by an Ising model, and the
elementary excitations are domain walls, or spinons. This is further evidenced
by the experimental finding that, upon applying a transverse field, the low-
energy properties of the system is controlled by a 1D quantum critical point
(QCP) belonging to the transverse field Ising universality, which is hidden
inside a 3D magnetically ordered phase [13].

CoNb2O6 is one compound in a large family of q1D magnets [23]. Recently, its
$S=1$ counterpart, NiNb2O6, has been studied [17, 18]. Similar to CoNb2O6,
NiNb2O6 also exhibits Ising anisotropy, and the ground state undergoes a FM to
paramagnetic (PM) quantum phase transition under a transverse field [24, 25].
Thermal transport measurements found similar behaviors of the thermal
conductivity near the quantum phase transitions of both CoNb2O6 and
NiNb2O6.[18] However, recent THz spectroscopy measurements [17] revealed a
magnon-like excitation mode in NiNb2O6, implying very different underlying
physics of these two materials. Theoretical study showed that the effective
model of NiNb2O6 is the FM $S=1$ Heisenberg chain, and the Ising anisotropy
comes from the single-ion anisotropy, which is weak compared to the Heisenberg
exchange interaction [17, 19, 20]. As a result, the elementary excitation of
the NiNb2O6 system is a magnon. It has been demonstrated based on experiment
and spin-wave theory, that magnon-magnon interaction plays a crucial role in
understanding the temperature dependence of the spin gap in NiNb2O6.[19] One
then wonder the spectral signatures of single and multiple magnons, and how
the spin excitation spectrum would evolve with field and temperature. The
linear spin-wave theory works well at zero temperature and in the zero and
large field limits. However, it would be complicated to apply this theory to
finite temperature, and the applicability of the theory to generic field
values has to be justified.

Motivated by recent progress on NiNb2O6 and the open theoretical questions, in
this work, we examine the spin dynamics of an effective 1D spin model for
NiNb2O6 via a simple semiclassical approach, which combines the numerical
techniques of classical Monte Carlo (MC) and molecular dynamics (MD)
simulations. This method allows us to access to spin dynamics of the system on
both sides of the quantum phase transition. We calculate the spin dynamical
structure factor (DSF) and confirm a magnon dispersion in the transverse
component of the DSF. Remarkably, we find two continua excitations in the
longitudinal channel at finite temperatures, and show that they are associated
with single- and two-magnon excitations, respectively. Our study reveal the
importance of the single-ion anisotropy for the the observed two-magnon
continuum. We discuss ways in probing these spectral signatures in NiNb2O6 and
other q1D magnets with large spin size.

##  2 Model and Methods

We study an effective 1D $S=1$ FM Heisenberg model for NiNb2O6. The model
Hamiltonian reads as

$H=-J\sum_{i}\mathbf{S}_{i}\cdot\mathbf{S}_{i+1}-D\sum_{i}(S^{z}_{i})^{2}-gh_{x}\sum_{i}S^{x}_{i},$
(1)

where $J>0$ is the FM interaction along the chain, $D>0$ is the easy-axis
single-ion anisotropy, and $h_{x}$ denotes the applied transverse magnetic
field with gyromagnetic factor $g$. For NiNb2O6, $J\sim 10$-$15$ K, $D\sim 5$,
and $g\approx 2.3$.[24, 25] In this work, we set $J=1$ as the energy unit and
take $D=0.5$ in the numerical simulations.

We investigate the spin dynamics of the model in Eq. (1) via a semiclassical
method by using classical MC and MD simulations [21, 22]. An individual
simulation consists of two major stages as described below.

First, by treating spins as classical vectors, a classical MC simulation is
employed to obtain the thermodynamic properties of the system and to generate
spin configurations in equilibrium for the MD simulation. In the MC
simulation, the length of a spin is set to $1$. We then sample in the
$(\cos\theta,\phi)$ space to ensure the uniform sampling in the entire spin
configuration space. The variation $(\delta\cos\theta,\delta\phi)$ is adjusted
during the thermalization of a simulation so that the acceptance rate stays
close to $50\%$ within the temperature range we considered. We further
implement an overrelaxation algorithm [26, 27] to reduce the autocorrelation
time. During every overrelaxation, we perform a specular reflection of the
local spin $\mathbf{S}_{i}$ about the local field $\mathbf{h}_{i}$ exerted on
it within the plane spanned by $S_{i}^{z}$ and $\mathbf{h}_{i}$. In practice,
an overrelaxation is performed when the spin configuration is not accepted at
a MC update.

During the MC simulation, we calculate the magnetic susceptibility $\chi$ with
respect to the applied field via

$\displaystyle\chi$
$\displaystyle=\frac{1}{NT}(<(\sum_{i}S^{x}_{i})^{2}>-<\sum_{i}S^{x}_{i}>^{2})$
(2)

where $T$ is the temperature and $N$ represents the number of total spins.

In the next step, we obtain the spin dynamics of the system via solving the
equation of motion (EOM) for each spin:

$\frac{d}{dt}\mathbf{S}_{i}(t)=i[H(t),\mathbf{S}_{i}(t)],$ (3)

where $\mathbf{S}_{i}(t)=e^{iHt}\mathbf{S}_{i}e^{-iHt}$ is the spin operator
in the Heisenberg representation. We solve the above EOM via the MD
simulation. To be specific, we start from the spin configuration generated by
the MC algorithm. $\mathbf{S}_{i}(t)$ of each spin is then determined from the
integration of coupled EOMs in Eq. (3).[28] These equations are numerically
integrated by a vectorized fourth-order predictor-corrector method [29]. We
carry the integration up to a maximum time $t_{max}=100/J$, with a time step
$\Delta=0.01/J$.

The DSF $S(\mathbf{q},\omega)$ is then calculated via

$\displaystyle S^{\alpha\alpha}(\mathbf{q},\omega)$
$\displaystyle=\sum_{i,j}e^{i\mathbf{q}\cdot(\mathbf{r}_{i}-\mathbf{r}_{j})}\int_{-\infty}^{\infty}\left[\langle
S^{\alpha}_{i}(t)S^{\alpha}_{j}(0)\rangle-\langle
S^{\alpha}_{i}(t)\rangle\langle S^{\alpha}_{j}(0)\rangle\right]e^{i\omega
t}dt,$ (4)

where $\alpha=x,y,z$. Note that we have used Simpson’s rule [29] for the
numerical integration involved in Eq. (4), and for the time integration in Eq.
(4), we took the time interval to be 0.1$J^{-1}$. To obtain good statistics,
each DSF is averaged over $100$ MD simulations with independent spin
configurations. In the simulation, we have taken a chain of length $L=100$ and
with periodic boundary condition. The finite-size effect is found to be
negligible.

We compare our numerical results with those of the linear spin-wave theory,
which we outline below. We first treat the $h_{x}=0$ case in the FM state.
From the Hamiltonian in Eq. (1), we perform a Holstein-Primakoff (H-P)
transformation to map the spin Hamiltonian to that of interacting bosons
(magnons). We then get the magnon dispersion

$\epsilon_{q}=2J(1-\cos q)+D.$ (5)

In the PM state driven by the transverse field $h_{x}$, we can construct a
spin-wave theory in the large $h_{x}$ limit. In this limit, the ground state
corresponds to a configuration that all spins are fully polarized to the
$S^{x}$ direction by the transverse field. The elementary excitation is then a
magnon (spin wave) where one spin deviates from the ground-state
configuration. To see this explicitly, we first perform a rotation of $\pi/2$
about the $S^{y}_{i}$ axis for each spin. This sends $S^{x}_{i}\rightarrow
S^{z}_{i}$ and $S^{z}_{i}\rightarrow-S^{x}_{i}$. We then make use of

$(S^{x}_{i})^{2}=\frac{1}{4}[(S^{+}_{i})^{2}+(S^{-}_{i})^{2}]+\frac{1}{2}[S^{2}-(S^{z}_{i})^{2}].$
(6)

The Hamiltonian in the rotated basis is then rewritten as

$H=-J\sum_{i}\mathbf{S}_{i}\cdot\mathbf{S}_{i+1}-gh_{x}\sum_{i}S^{z}_{i}+\frac{D}{2}\sum_{i}(S^{z}_{i})^{2}-\frac{D}{4}\sum_{i}[(S^{+}_{i})^{2}+(S^{-}_{i})^{2}],$
(7)

We can then perform a H-P transformation in this rotated basis. The transverse
field $h_{x}$ (longitudinal field in the rotated basis) corresponds to the
chemical potential of the magnons. The penultimate term acts as a repulsive
Coulomb interaction between magnons, and the last term refers to creating and
annihilating two magnons on a site. In the single-magnon sector, the spin-wave
(single-magnon) dispersion reads

$\epsilon_{q}=2J(1-\cos q)-D/2+gh_{x}.$ (8)

The energy-momentum relation of the two-magnon continuum reads

$\omega_{2}(q,k)=\epsilon_{k+q}+\epsilon_{k}=4J[1-\cos\frac{q}{2}\cos(k+\frac{q}{2})]-D+2gh_{x}.$
(9)

##  3 Phase diagram and field evolution of the spin gap

Figure 1:  The phase diagram in the field-temperature plane and the field
dependent spin gap. The green curve with circles represents the spin gap
extracted from the transverse DSF $S^{yy}(q,\omega)$ at $q=0$ and $T=0.01$.
The dashed line with magenta squares shows a crossover between classical
renormalized and disordered regimes, which is determined from the peak
position of the field dependent susceptibility (see Fig. 2). These field
dependent behaviors indicate a FM to PM quantum phase transition with QCP
located at $h_{x}^{c}\approx 0.4$.

At zero field, the model in Eq. (1) has a FM Ising ordered ground state.
Because of the single-ion anisotropy $D$, the spins are lined up along the
$S^{z}$ direction. The transverse field $h_{x}$ suppresses the Ising order by
aligning spins in the $S^{x}$ direction, and turns the FM ground state to a PM
one via a quantum phase transition at $h_{x}^{c}$ (see Fig. 1). In a 1D
system, the FM order is stabilized only at $T=0$, but finite-temperature
crossovers can still be observed. We calculated the field dependent transverse
susceptibility $\chi$ from the MC simulations at several temperatures. As
shown in Fig. 2(a), with increasing $h_{x}$, $\chi$ first increases, develops
a peak, then is quickly suppressed. The peak signals a crossover from the
classical renormalized regime to the disordered regime, shown as the dashed
line with square symbols in Fig. 1. Note that quantum fluctuations are not
captured by our classical MC simulations, therefore the quantum critical
regime in the vicinity of a QCP is not identified. However, we can determine
the position of the QCP by extrapolating the crossover line to the $T=0$
limit. This gives $h_{x}^{c}/J\approx 0.4$.

Figure 2:  (a): Field dependent magnetic susceptibility $\chi$ at several
temperatures. The peak indicates a crossover between the classical
renormalized and disordered regimes. (b): The transverse DSF
$S^{yy}(q,\omega)$ at $q=0$ and $T=0.01$. The energy of the peak in each curve
determines the spin gap shown in Fig. 1.

We then calculate the transverse component of the DSF $S^{yy}(q=0,\omega)$ at
$T=0.01$ via the semiclassical MD method. As shown in Fig. 2(b),
$S^{yy}(q=0,\omega)$ shows a single peak at finite energy $\omega$, indicating
a gapped excitation. At this low temperature, the spins are converged to their
ground-state configuration. It is then expected that the DSF is characterized
by the excitation from the ground state to the lowest excited state. The
extracted spin gap (in Fig. 1) first decreases with increasing the field
$h_{x}$ until it closes at $h_{x}/J\approx 0.4$. The gap then reopens in
higher fields. The gap closing and reopening behavior is consistent with that
of a FM transverse field Ising chain, demonstrating clearly the FM to PM
transition in the ground state. The critical field value extrapolated from the
DSF agrees well with that from the susceptibility.

##  4 Spin excitation spectra

Figure 3:  Spin excitation spectra of $S^{xx}(q,\omega)$ [in (a) and (c)] and
$S^{zz}(q,\omega)$ [in (b) and (d)] at $T=0.1$ for $h_{x}=0$ (upper panels)
and $h_{x}=1$ (lower panels). The solid lines depict single magnon (spin wave)
dispersion. The dash-dotted lines refer to the boundaries of the continua
associated with one-magnon excitations. The dashed lines show boundaries of
the two-magnon continua. See text for more information.

With the phase diagram settled, we now examine the low-energy excitations of
the system. At zero temperature, the low-energy spin excitations in either the
FM or the PM phase is described by the spin-wave theory presented in Sec. 2 .
The elementary excitation is a magnon which characterizes the deviation from
the fully polarized spin state along either $S_{z}$ or $S_{x}$ direction,
depending on the field. In Fig. 3, we present calculated $S^{xx}(q,\omega)$
and $S^{zz}(q,\omega)$ at finite momentum $q$ for two field values $h_{x}=0$
and $h_{x}=1$ at $T=0.1$. We see that the transverse mode, $S^{xx}(q,\omega)$
in the FM and $S^{zz}(q,\omega)$ in the PM state, displays clearly a
dispersive magnon band. However, by fitting the numerical magnon dispersions
to Eqs. (5) and (8), we find they better fit to $\epsilon_{q}=2J(1-\cos q)+2D$
at $h_{x}=0$ and $\epsilon_{q}=2J(1-\cos q)-D+gh_{x}$ at $h_{x}=1$. Compared
to the spin-wave theory, $D$ is doubled. The discrepancy comes from the
semiclassical approximation to the single-ion anisotropy term. The EOM for
$S^{x}_{i}$ associated with this term reads,
$\frac{d}{dt}S^{x}_{i}(t)=i[D(S^{z}_{i})^{2},S^{x}_{i}]=D(S^{y}_{i}S^{z}_{i}+S^{z}_{i}S^{y}_{i})$.
For $S=1$, the term on the right-hand side corresponds to a quadrupolar
operator. However, by treating the spin operators as classical vectors, we
take the following approximation
$D(S^{y}_{i}S^{z}_{i}+S^{z}_{i}S^{y}_{i})\approx 2DS^{y}_{i}S^{z}_{i}$ when
performing the MD simulation. This approximation causes the double counting of
the $D$ term, as appeared in the magnon dispersion in MD simulations. Note
that this issue only leads to a global shift of the spin gap, but will not
affect the shape of the dispersion.

Next, we investigate the longitudinal modes, which correspond to
$S^{zz}(q,\omega)$ in the FM and $S^{xx}(q,\omega)$ in the PM state. These
modes exhibit more interesting features. As shown in Fig. 3(b) and (c), for
both $h_{x}=0$ and $h_{x}=1$, the longitudinal modes exhibit prominent gapless
continua extending to the Brillouin zone (BZ) boundary. This is rather
surprising. First, a continuum is usually associated to fractionalized spin
excitations, but for a FM Heisenberg chain, the elementary excitation is a
magnon carrying $S=1$. Moreover, even the continuum of an Ising chain is
gapped when the system is away from the QCP.

To understand the nature of these continuous excitations, we note that the
spectral weights of the longitudinal excitations are much weaker than those of
the transverse modes. This implies that the observed continua are finite-
temperature effects. At finite temperature, the magnon density is nonzero.
These magnons reside in the single magnon band, and can be further excited.
Assuming a magnon residing on the state with momentum $k$ and energy
$\epsilon_{k}$, it can be excited to another state in the magnon band with
momentum $k+q$ and energy $\epsilon_{k+q}$. The excitation energy is then

$\omega(q,k)=\epsilon_{k+q}-\epsilon_{k}=4J\sin\frac{q}{2}\sin(k+\frac{q}{2}),$
(10)

forming a gapless continuum with half-bandwidth of $4J$. Note that this
process only alters the energy and momentum of a magnon, but does not modify
the magnon density. So it shows up in the longitudinal channel. Also note that
it relies on a finite magnon density in the initial state, which is possible
only at finite temperature. This type of excitations is exactly the gapless
continua observed in Fig. 3(b) and (c), on both the FM and PM sides of the
phase diagram.

Besides this gapless continuum, we observe another gapped continuum in the
longitudinal mode at $h_{x}=1$ on the PM side. Numerically, we find it fits to
the energy-momentum relation of two-magnon excitations in Eq. (9) when we
substitute $2D$ for $D$. This implies that this continuum originates from two-
magnon excitations. But we need to understand why these excitations are only
observed in the PM phase and in the longitudinal channel.

The answer to these questions lies in the Hamiltonian in the rotated basis of
Eq. (7). The last term of this Hamiltonian contains a $(S^{+}_{i})^{2}$
process, which generates a two-magnon bound state (with a pair of magnons on
one site) from the fully polarized (zero magnon) state. As a result, the
ground state is a superposition of the zero- and two-magnon states. It is then
possible that the magnon density does not change when exciting from the ground
state to the two-magnon continuum, which must take place in the longitudinal
channel. This is indeed what is observed in the numerical results. In the FM
state, from Eq. (1) we see that the $(S^{+}_{i})^{2}$ process is missing in
the Hamiltonian. The two-magnon state is not mixed to the ground state and
hence a two-magnon continuum is not observed.

Next we examine the evolution of these continua in the longitudinal
excitations with temperature. In Fig. 4 we show $S^{xx}(q,\omega)$ at
$h_{x}=1$ in the PM state for two temperatures $T=0.5$ and $T=1$. Compared to
$S^{xx}(q,\omega)$ at $T=0.1$ in Fig. 3(c), we see two major features: First,
with increasing temperature, the overall spectral weights initially increases,
then decreases; second, the bandwidths of both continua decrease with
increasing temperature. The initial increase of spectral weights of the
continua is due to the larger (multi-)magnon population at higher temperature.
The spectral weights then decay as temperature futher increases. The second
feature is associated with the magnon-magnon interaction. As we discussed in
Sec.2 , the $\frac{D}{2}(S^{z}_{i})^{2}$ term in Eq. (7) acts as a repulsive
onsite interaction between magnons. With increasing temperature, the
localization effects caused by this term leads to suppression of both
bandwidth and spectral weight of the transverse single-magnon mode (not
shown). Accordingly, the bandwidths of the two continua in the longitudinal
mode are also suppressed. For the two-magnon continuum, since the bandwidth
suppression is about the center of the continuum, effectively, the two-magnon
spin gap at $q=0$ increases with increasing temperature.

Figure 4:  $S^{xx}(q,\omega)$ at $h_{x}=1$ and temperatures $T=0.5$ [in (a)]
and $T=1.0$ [in (b)], respectively. The dashed and dash-dotted lines show
boundaries of magnon continua at zero temperature according to the spin-wave
theory.

##  5 Discussions and conclusions

In this work, we have investigated spin dynamics of an $S=1$ ferromagnetic
Heisenberg model with single-ion anisotropy by using a semiclassical MD
method. We show that the magnetic responses and evolution of the spin gap with
the applied transverse magnetic field is well described by our numerical
approach. We further study the DSF of this model, and find a magnon dispersion
in the transverse component. Interestingly, we find two continua excitations
in the longitudinal component of DSF at finite temperature. Based on spin-wave
analysis, these two continua are ascribed to single- and two-magnon
excitations, respectively. We show that the single-ion anisotropy couples the
2-magnon bound state to the 0-magnon ground state, which is crucial for the
observation of the two-magnon continuum in the longitudinal excitation
spectra. Note that this mechanism does not exist in the $S=1/2$ model, but is
generic for Heisenberg models with $S\geqslant 1$. Our model is pertinent to
the $S=1$ spin chain compound NiNb2O6 and other q1D magnets with large spin
size [30]. Our results also suggest that a very different low-energy spin
dynamics in NiNb2O6 from its effective spin $S=1/2$ counterpart, CoNb2O6,
though both compounds exhibit easy-axis anisotropy. The calculated spin
dynamics, especially the continua in spin excitation spectra can be verified
by various experiments including inelastic neutron scattering and Raman
scattering.

## Acknowledgment

We thank J. Dai for useful discussions. Financial supports are given in the
footnote on the first page.

## References

  * [1] Giamarchi T  2004 Quantum Physics in One Dimension (New York:Oxford Science)
  * [2] Chen X, Gu Z C, Liu Z X, and Wen X G 2012 Science 338 1604
  * [3] Cui Y, Zou H, Xi N, He Z Z, Yang Y X, Shu L, Zhang G H, Hu Z, Chen T, Yu R, Wu J D, and Yu W Q  2019 Phys. Rev. Lett 123 067203
  * [4] Faure Q, Takayoshi S, Petit S, Simonet V, Raymond S, Regnault L P, Boehm M, White J S, Mȧnsson M, Rüegg C, Lejay P, Canals B, Lorenz T, Furuya S C, Giamarchi T, and Grenier B 2018 Nat. Phys 14 716
  * [5] Wang Z, Wu J D, Yang W, Bera A K, Kamenskyi D, Islam A T M N, Xu S L, Law J M, Wu C J, and Loidl A 2018 Nature 554 219
  * [6] Zou H Y, Cui Y, Wang X, Zhang Z, Yang J, Xu G, Okutani A, Hagiwara M, Matsuda M, Wang G, Mussardo G H$\acute{\mathrm{o}}$ds$\acute{\mathrm{a}}$gi K, Kormos M, He Z Z, Kimura S, Yu R, Yu W Q, Ma J, and Wu J D  2021 Phys. Rev. Lett 127 077201
  * [7] Nikitin S E, Nishimoto S, Fan Y, Wu J, Wu L S, Sukhanov A S, Brando M, Pavlovskii N S, Xu J, Vasylechko L, Yu R, and Podlesnyak A 2021 Nat. Commun 12 3599
  * [8] Roberts B, Jiang S H, and Motrunich O I  2019 Phys. Rev. B 99 165143
  * [9] Xi N and Yu R 2022 Chin. Phys. B 31 057501
  * [10] Schollwöck U, Richter J, Farnell D J J, and Bishop R F 2008 Quantum Magnetism(Berlin Heidelberg:Springer) p.307
  * [11] Coldea R, Tennant D A, Wheeler E M, Wawrzynska E, Prabhakaran D, Telling M, Habicht K, Smeibidl P, and Kiefer K 2010 Science 327 177
  * [12] Lee S B, Kaul R K, and Balents L 2010 Nat. Phys 6 702
  * [13] Kinross A W, Fu M, Munsie T J, Dabkowska H A, Luke G M, Sachdev S, and Imai T 2014 Phys. Rev. X 4 031008
  * [14] Morris C M, Desai N, Viirok J, Hüvonen D, Nagel D, Rõõm T, Krizan J W, Cava R J, McQueen T M, Koohpayeh S M, Kaul R K and Armitage N P 2021 Nat. Phys 17 832
  * [15] Fava M, Coldea R, and Parameswaran S A 2020 Proc. Nat. Acad. Sci. U.S.A. 117 25219
  * [16] Gallegos C A and Chernyshev A L arXiv:2312.03829
  * [17] Chauhan P, Mahmood F, Changlani H J, Koohpayeh S M, and Armitage N P 2020 Phys. Rev. Lett 124 037203
  * [18] Xu Y, Wang L S, Huang Y Y, Ni J M, Zhao C C, Dai Y F, Pan B Y, Hong X C, Chauhan P, Koohpayeh S M, Armitage N P, and Li S Y 2022 Phys. Rev. X 12 021020
  * [19] Sharma P, Lee K, and Changlani H 2022 Phys. Rev. B 105 054413
  * [20] Nayak M and Mila F 2022 Phys. Rev. B 105 094407
  * [21] Chen K and Landau D P  1994 Phys. Rev. B 49 3266
  * [22] Bunker A, Chen K and Landau D P  1996 Phys. Rev. B 54 9259
  * [23] Weitzel V H  1976 Zeitschrift für Kristallographie, Bd 144 S. 238
  * [24] Heid C, Weitzel H, Bourdarot F, Calemczuk R, Vogt T, and H. Fuess  1996 J. Phys. Condens. Matter 8 10609
  * [25] Yaeger I, Morrish A H, and Wanklyn B M  1977 Phys. Rev. B 15 1465
  * [26] Brown F R and Woch T J  1987 Phys. Rev. Lett 58 2394
  * [27] Creutz M  1987 Phys. Rev. D 36 515
  * [28] Watson R E, Blume M, and Vineyard G H  1969 Phys. Rev 181 811
  * [29] Burden R L, Fairas J D, and Reynolds A C  2011 Numerical Analysis(Brooks/Cole Cengage Learning) p.311
  * [30] Curley S P M, Scatena R, Williams R C, Goddard P A, Macchi P, Hicken T J, Lancaster T, Xiao F, Blundell S J, Zapf V, Eckert J C, Krenkel E H, Villa J A, Rhodehouse M L, and Manson J L 2021 Phys. Rev. Mater 5 034401