# Edge coloring graphs with large minimum degree

Michael J. Plantholt and Songling Shan
Illinois State University, Normal, IL 61790
<EMAIL_ADDRESS><EMAIL_ADDRESS>
_Abstract._ Let $G$ be a simple graph with maximum degree $\Delta(G)$. A
subgraph $H$ of $G$ is overfull if $|E(H)|>\Delta(G)\lfloor|V(H)|/2\rfloor$.
Chetwynd and Hilton in 1985 conjectured that a graph $G$ with
$\Delta(G)>|V(G)|/3$ has chromatic index $\Delta(G)$ if and only if $G$
contains no overfull subgraph. The 1-factorization conjecture is a special
case of this overfull conjecture, which states that for even $n$, every
regular $n$-vertex graph with degree about $n/2$ has a 1-factorization and was
confirmed for large graphs in 2014. Supporting the overfull conjecture as well
as generalizing the 1-factorization conjecture in an asymptotic way, in this
paper, we show that for any given $0<\varepsilon<1$, there exists a positive
integer $n_{0}$ such that the following statement holds: if $G$ is a graph on
$2n\geq n_{0}$ vertices with minimum degree at least $(1+\varepsilon)n$, then
$G$ has chromatic index $\Delta(G)$ if and only if $G$ contains no overfull
subgraph.

_Keywords._ Chromatic index; 1-factorization; overfull conjecture; overfull
graph.

##  1 Introduction

In this paper, a graph means a simple graph and a multigraph may contain
parallel edges but no loops. Let $G$ be a multigraph. Denote by $V(G)$ and
$E(G)$ the vertex set and edge set of $G$, respectively, and by $e(G)$ the
cardinality of $E(G)$. For $v\in V(G)$, $N_{G}(v)$ is the set of neighbors of
$v$ in $G$, and $d_{G}(v)$, the degree of $v$ in $G$, is the number of edges
of $G$ that are incident with $v$. When $G$ is simple, $d_{G}(v)=|N_{G}(v)|$.
For $S\subseteq V(G)$, $N_{G}(S)=\bigcup_{v\in S}N_{G}(v)$, the subgraph of
$G$ induced on $S$ is denoted by $G[S]$, and $G-S:=G[V(G)\setminus S]$. If
$F\subseteq E(G)$, then $G-F$ is obtained from $G$ by deleting all the edges
of $F$. Let $V_{1},V_{2}\subseteq V(G)$ be two disjoint vertex sets. Then
$E_{G}(V_{1},V_{2})$ is the set of edges in $G$ with one end in $V_{1}$ and
the other end in $V_{2}$, and $e_{G}(V_{1},V_{2}):=|E_{G}(V_{1},V_{2})|$. We
write $E_{G}(v,V_{2})$ and $e_{G}(v,V_{2})$ if $V_{1}=\\{v\\}$ is a singleton.
Define $\mu(G)=\max\\{e_{G}(u,v)\,:\,u,v\in V(G)\\}$ to be the multiplicity of
$G$. We also write $G[V_{1},V_{2}]$ to denote the bipartite subgraph of $G$
with vertex set $V_{1}\cup V_{2}$ and edge set $E_{G}(V_{1},V_{2})$.

For two integers $p,q$, let $[p,q]=\\{i\in\mathbb{Z}\,:\,p\leq i\leq q\\}$. An
edge $k$-coloring of a multigraph $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$.

In 1960’s, Gupta [10] and, independently, Vizing [24] proved that for all
graphs $G$, $\Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1$. This leads to a
natural classification of simple graphs. Following Fiorini and Wilson [7], we
say a graph $G$ is of class 1 if $\chi^{\prime}(G)=\Delta(G)$ and of _class 2_
if $\chi^{\prime}(G)=\Delta(G)+1$. Holyer [12] showed that it is NP-complete
to determine whether an arbitrary graph is of class 1. Nevertheless, if
$|E(G)|>\Delta(G)\lfloor|V(G)|/2\rfloor$, then we have to color $E(G)$ using
exactly $(\Delta(G)+1)$ colors. Such graphs are _overfull_. An overfull
subgraph $H$ of $G$ with $\Delta(H)=\Delta(G)$ is called a _$\Delta(G)$
-overfull subgraph_ of $G$. A number of long-standing conjectures listed in
Twenty Pretty Edge Coloring Conjectures in [22] lie in deciding when a graph
is overfull. Chetwynd and Hilton [2, 3], in 1986, proposed the following
conjecture.

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

Let $G$ be a simple graph with $\Delta(G)>\frac{1}{3}|V(G)|$. Then
$\chi^{\prime}(G)=\Delta(G)$ if and only if $G$ contains no
$\Delta(G)$-overfull subgraph.

The $3$-critical graph $P^{*}$, obtained from the Petersen graph by deleting
one vertex, satisfies $\Delta(P^{*})=\frac{1}{3}|V(P^{*})|$ but contains no
3-overfull subgraph. Thus the degree condition $\Delta(G)>\frac{1}{3}|V(G)|$
in the conjecture above is best possible. Applying Edmonds’ matching polytope
theorem, Seymour [20] showed that whether a graph $G$ contains an overfull
subgraph of maximum degree $\Delta(G)$ can be determined in polynomial time.
Thus 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(G)>\frac{1}{3}|V(G)|$. Despite its importance, very little is
known about the truth of the overfull conjecture. It was confirmed only for
graphs with $\Delta(G)\geq|V(G)|-3$ by Chetwynd and Hilton [3] in 1989. By
restricting the minimum degree, Plantholt [19] 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, which in 2013 was
confirmed for large graphs by Csaba, Kühn, Lo, Osthus and Treglown [5]. The
overfull conjecture was also confirmed for dense quasirandom graphs [8, 21].
In this paper, in supporting the overfull conjecture as well as generalizing
the 1-factorization conjecture in an asymptotic way, we obtain the result
below.

######  Theorem 1.2.

For all $0<\varepsilon<1$, there exists $n_{0}$ such that the following
statement holds: if $G$ is a graph on $2n\geq n_{0}$ vertices with
$\delta(G)\geq(1+\varepsilon)n$, then $\chi^{\prime}(G)=\Delta(G)$ if and only
if $G$ contains no $\Delta(G)$-overfull subgraph. Furthermore, there is a
polynomial time algorithm that finds an optimal coloring.

The proof of Theorem 1.2 is based on the following result.

######  Theorem 1.3.

For all $0<\varepsilon<1$, there exists $n_{0}$ such that the following
statement holds. If $G$ is a graph on $2n\geq n_{0}$ vertices satisfying one
of the following three conditions:

  1. (a)

$G$ is regular with $\delta(G)\geq(1+4\varepsilon/5)n$,

  2. (b)

$G$ has two distinct vertices $x,y$ such that
$d(x)=d(y)\geq(1/2+3\varepsilon/2)n$, for all $z\in V(G)\setminus\\{x,y\\}$,
$d(z)=\Delta(G)\geq(1+\varepsilon)n$, and
$\Delta(G)-\delta(G)\leq(1/2-\varepsilon/2)n$,

  3. (c)

$\Delta(G)-\delta(G)\geq n^{6/7}$, $|V_{\delta}|\geq n^{6/7}$ and
$|V_{\Delta}|\geq n+1$, and $\delta(G)\geq(1+\varepsilon)n$,

then $\chi^{\prime}(G)=\Delta(G)$. Furthermore, there is a polynomial time
algorithm that finds an optimal coloring.

The remainder of this paper is organized as follows. In the next section, we
introduce some notation and preliminary results. In Section 3, we prove
Theorem 1.2 by applying Theorem 1.3. Theorem 1.3 is then proved in the last
section.

##  2 Notation and preliminaries

Let $G$ be a multigraph and $\varphi\in\mathcal{C}^{k}(G)$ for some integer
$k\geq 0$. For any $v\in V(G)$, the set of colors _present_ at $v$ is
$\varphi(v)=\\{\varphi(e)\,:\,\text{$e$ is incident with $v$}\\}$, and the set
of colors _missing_ at $v$ is
$\overline{\varphi}(v)=[1,k]\setminus\varphi(v)$. For a subset $X$ of $V(G)$
and a color $i\in[1,k]$, define $\overline{\varphi}_{X}^{-1}(i)=\\{v\in
X:i\in\overline{\varphi}(v)\\}$, and we write $\overline{\varphi}^{-1}(i)$ for
$\overline{\varphi}_{V(G)}^{-1}(i)$. An edge $k$-coloring of a multigraph $G$
is said to be _equalized_ if each color class contains either
$\lfloor|E(G)|/k\rfloor$ or $\lceil|E(G)|/k\rceil$ edges.

For $x\in V(G)$, the _deficiency_ of $x$ in $G$ is
$\operatorname{def}_{G}(x):=\Delta(G)-d_{G}(x)$. For $X\subseteq V(G)$,
$\operatorname{def}_{G}(X)=\sum_{x\in X}\operatorname{def}_{G}(x)$. We simply
write $\operatorname{def}_{G}(V(G))$ as $\operatorname{def}(G)$. A subgraph
$H$ of $G$ with an odd order is _$\Delta(G)$ -full_ if
$|E(H)|=\Delta(G)\lfloor|V(H)|/2\rfloor$. Define $V_{i}(G)=\\{v\in
V(G):d_{G}(v)=i\\}$, and we write $V_{i}$ for $V_{i}(G)$ if $G$ is clear.

We will use the following notation: $0<a\ll b\leq 1$. Precisely, if we say a
claim is true provided that $0<a\ll b\leq 1$, then this means that there
exists a non-decreasing function $f:(0,1]\rightarrow(0,1]$ such that the
statement holds for all $0<a,b\leq 1$ satisfying $a\leq f(b)$.

In 1960’s, Gupta [10] and, independently, Vizing [24] provided an upper bound
on the chromatic index of multigraphs, and König [14] gave an exact value of
the chromatic index for bipartite multigraphs.

######  Theorem 2.1 ([10, 24]).

Every multigraph $G$ satisfies $\chi^{\prime}(G)\leq\Delta(G)+\mu(G)$.

######  Theorem 2.2 ([14]).

Every bipartite multigraph $G$ satisfies $\chi^{\prime}(G)=\Delta(G)$.

McDiarmid [15] observed the following result.

######  Theorem 2.3.

Let $G$ be a multigraph with chromatic index $\chi^{\prime}(G)$. Then for all
$k\geq\chi^{\prime}(G)$, there is an equalized edge-coloring of $G$ with $k$
colors.

Let $G$ be a multigraph, $k\geq 0$ be an integer and
$\varphi\in\mathcal{C}^{k}(G)$. There is a polynomial time algorithm to modify
$\varphi$ into an equalized edge-coloring of $G$ with $k$ colors. To see this,
suppose $\varphi$ is not equalized and so we take two colors $i,j\in[1,k]$
such that
$\left||\overline{\varphi}^{-1}(i)|-|\overline{\varphi}^{-1}(j)|\right|$ is
largest. Since $\varphi$ is not equalized,
$\left||\overline{\varphi}^{-1}(i)|-|\overline{\varphi}^{-1}(j)|\right|\geq
4$. Assume by symmetry that
$|\overline{\varphi}^{-1}(i)|-|\overline{\varphi}^{-1}(j)|\geq 4$. Consider
the submultigraph of $G$ induced on the set of edges colored by $i$ or $j$,
then the submultigraph must have a component that is a path $P$ starting at an
edge colored by $j$ and ending at an edge colored by $j$. By swapping the
colors $i$ and $j$ along this path $P$, we decreased
$|\overline{\varphi}^{-1}(i)|-|\overline{\varphi}^{-1}(j)|$ by 4. Repeating
this process, we can obtain an equalized edge-coloring of $G$ with $k$ colors
after at most $k^{2}|V(G)|$ rounds.

Given an edge coloring of $G$ and a given color $i$, since vertices presenting
$i$ are saturated by the matching consisting of all edges colored by $i$, we
have the Parity Lemma below. The result had appeared in many papers, for
example, see [9, Lemma 2.1].

######  Lemma 2.4 (Parity Lemma).

Let $G$ be a multigraph and $\varphi\in\mathcal{C}^{k}(G)$ for some integer
$k\geq\Delta(G)$. Then $|\overline{\varphi}^{-1}(i)|\equiv|V(G)|\pmod{2}$ for
every color $i\in[1,\Delta(G)]$.

We need the following classical result of Hakimi [11] on multigraphic degree
sequence.

######  Theorem 2.5.

Let $0\leq d_{n}\leq\ldots\leq d_{1}$ be integers. Then there exists a
multigraph $G$ on vertices $x_{1},\ldots,x_{n}$ such that $d_{G}(x_{i})=d_{i}$
for all $i$ if and only if $\sum_{i=1}^{n}d_{i}$ is even and
$\sum_{i>1}d_{i}\geq d_{1}$.

Though it is not explicitly stated in [11], the inductive proof yields a
polynomial time algorithm which finds an appropriate multigraph if it exists.

######  Theorem 2.6 ([6]).

Let $G$ be a graph on $n\geq 3$ vertices. If $\delta(G)\geq\frac{n}{2}$, then
$G$ is hamiltonian; and if $\delta(G)\geq\frac{n+1}{2}$, then $G$ is
hamiltonian-connected.

######  Lemma 2.7.

Let $G$ be an $n$-vertex simple graph such that all vertices of degree less
than $\Delta(G)$ are mutually adjacent in $G$. Then
$|V_{\Delta}|>\frac{n}{2}$.

Proof. Let $a=|V_{\Delta}|$ and $|V(G)\setminus V_{\Delta}|=n-a$ for some
integer $a$. For each $v\in V_{\Delta}$, note that $e_{G}(v,V(G)\setminus
V_{\Delta})\geq\Delta-(a-1)$. Since $V(G)\setminus V_{\Delta}$ is a clique in
$G$, for every $v\in V(G)\setminus V_{\Delta}$, $e_{G}(v,V(G)\setminus
V_{\Delta})<\Delta-(n-a-1)$. Therefore,

$\displaystyle(\Delta-(a-1))a$ $\displaystyle\leq
e_{G}(V_{\Delta},V(G)\setminus V_{\Delta})<$
$\displaystyle(n-a)(\Delta-(n-a-1)).$

Thus

$\displaystyle(\Delta-(a-1))a$ $\displaystyle<(n-a)(\Delta-(n-a-1))$
$\displaystyle\Rightarrow$ $\displaystyle\Delta a-a(a-1)$
$\displaystyle<(n-a)\Delta-(n-a)^{2}+(n-a)$ $\displaystyle\Rightarrow$
$\displaystyle\Delta(2a-n)+a-(n-a)$ $\displaystyle<2na-n^{2}$
$\displaystyle\Rightarrow$ $\displaystyle(\Delta+1)(2a-n)$
$\displaystyle<n(2a-n).$

Clearly, $2a-n\neq 0$. Since $\Delta+1\leq n$, it is easy to see that $2a-n>0$
and so $a>\frac{n}{2}$. ∎

The two lemmas below concern existences of overfull subgraphs in simple
graphs.

######  Lemma 2.8 ([18]).

Let $G$ be a simple graph of even order $n$ with $\delta(G)>\frac{n}{2}$. If
$H$ is an induced proper subgraph of $G$ such that $H$ is either
$\Delta(G)$-overfull or $\Delta(G)$-full, then $H=G-v$ for some vertex $v\in
V_{\delta}$.

######  Lemma 2.9.

Let $G$ be a simple graph of even order $n$ with $\delta(G)>\frac{n}{2}$. Then
$G$ contains no $\Delta(G)$-overfull subgraph if $|V_{\delta}|\geq 2$.

Proof. Let $x,y\in V_{\delta}$ be distinct. Then $\sum_{v\in
V(G-x)}(\Delta(G)-d_{G-x}(v))=d_{G}(x)+(\Delta(G)-d_{G}(y))+\operatorname{def}_{G}(V(G)\setminus\\{x,y\\})\geq\Delta(G)$.
Thus $G-x$ is not $\Delta(G)$-overfull. By Lemma 2.8, $G$ contains no
$\Delta(G)$-overfull subgraph. ∎

######  Lemma 2.10.

Let $0<\varepsilon<1$, $n_{0}$ be a positive integer, and $G$ be a graph on
$2n\geq n_{0}$ vertices with $\delta(G)\geq(1+\varepsilon)n$. If $G$ contains
a $\Delta(G)$-full subgraph, then $G$ contains a spanning $\delta(G)$-regular
subgraph obtained from $G$ by deleting $\Delta(G)-\delta(G)$ matchings
iteratively. As a consequence, $\chi^{\prime}(G)=\Delta(G)$. Furthermore,
there is a polynomial time algorithm that finds an optimal coloring.

Proof. Define $g=\Delta(G)-\delta(G)$. If $G$ is regular, then we are done by
Theorem 1.3. Thus $G$ is not regular and so $g\geq 1$. Since $G$ contains a
$\Delta(G)$-full subgraph, which by Lemma 2.8 must be $G-x$ for some vertex
$x\in V_{\delta}$. Also, if $G$ contains a $\Delta(G)$-overfull subgraph, then
$G-x$ must be $\Delta(G)$-overfull also by Lemma 2.8. Since $G-x$ is
$\Delta(G)$-full, we conclude that $G$ contains no $\Delta(G)$-overfull
subgraph and so has another vertex of degree less than $\Delta(G)$. We let
$y\in V(G)\setminus\\{x\\}$ such that $d_{G}(y)$ is smallest among all
vertices in $V(G)\setminus\\{x\\}$. Since $G-x$ is $\Delta(G)$-full, we have
$\Delta(G)=\operatorname{def}(G-x)=d_{G}(x)+(\Delta(G)-d_{G}(y))+\operatorname{def}_{G}(V(G)\setminus\\{x,y\\})$.
As $d_{G}(x)=\delta(G)$, if $d_{G}(y)=\delta(G)$, then
$\operatorname{def}_{G}(V(G)\setminus\\{x,y\\})=0$. This implies that if
$d_{G}(y)=\delta(G)$, then every vertex from $V(G)\setminus\\{x,y\\}$ has
degree $\Delta(G)$ in $G$; and if $d_{G}(y)>\delta(G)$, then as $y$ is chosen
to have smallest degree in $G$ among vertices from $V(G)\setminus\\{x\\}$,
$V(G)\setminus\\{x,y\\}$ contains no vertex of degree $\delta(G)$ in $G$.
Since $\delta(G-x-y)\geq\frac{n}{2}-1$, $G-x-y$ has a hamiltonian cycle by
Theorem 2.6. As $n-2$ is even, we know that $G-x-y$ has a perfect matching
$M_{1}$. Now we have $\delta(G-M_{1})=\delta(G)$ and
$\Delta(G-M_{1})-\delta(G-M_{1})=g-1<g$. Let $G_{1}=G-M_{1}$. Since

$\displaystyle\operatorname{def}(G_{1}-x)$ $\displaystyle=$ $\displaystyle
d_{G}(x)+(\Delta(G_{1})-d_{G}(y))+\operatorname{def}_{G_{1}}(V(G)\setminus\\{x,y\\})$
$\displaystyle=$ $\displaystyle
d_{G}(x)+\operatorname{def}_{G}(V(G)\setminus\\{x\\})-1$ $\displaystyle=$
$\displaystyle\operatorname{def}(G-x)-1=\Delta(G)-1=\Delta(G_{1}),$

we see that $G_{1}-x$ is $\Delta(G_{1})$-full. Thus we may repeat the
procedure, and reach a $\delta(G)$-regular graph $G^{*}$ after taking $g$
matchings $M_{1},\ldots,M_{g}$.

Now by Theorem 1.3, $\chi^{\prime}(G^{*})=\Delta(G^{*})=\delta(G)$. Coloring
each of the $g$ matchings $M_{1},\ldots,M_{g}$ using a different color
together with an edge $\delta(G)$-coloring of $G^{*}$ gives an edge
$\Delta(G)$-coloring of $G$. Thus $\chi^{\prime}(G)=\Delta(G)$.

It is polynomial-time to find a hamiltonian cycle in graphs $H$ with
$\delta(H)\geq\frac{1}{2}|V(H)|$ [16, Theorem 4]. Thus all the matchings
$M_{1},\ldots,M_{g}$ can be found in polynomial time. As an optimal edge
coloring can be found in polynomial time for graphs satisfying the conditions
in Theorem 1.3, we can find an edge $\delta(G)$-coloring of $G^{*}$ in
polynomial time. Therefore, there is a polynomial-time algorithm that finds an
edge $\Delta(G)$-coloring for $G$. ∎

######  Lemma 2.11.

Let $G[X,Y]$ be bipartite graph with $|X|=|Y|=n$. Suppose $\delta(G)=t$ for
some $t\in[1,n-1]$, and except at most $t/2$ vertices all other vertices of
$G$ have degree at least $(n+t/2)/2$ in $G$. Then $G$ has a perfect matching.

Proof. Let $W=\\{v\in V(G)\,:\,d_{G}(v)<(n+t/2)/2\\}$. As $|W|\leq t/2$ and
$\delta(G)\geq t$, we can greedily find in $G$ a matching $M_{1}$ that
saturates $W$ and has size $2|W|$. Let $W^{*}$ be the set of vertices of $G$
that are saturated by $M_{1}$, $G_{1}=G-W^{*}$, $X_{1}=X\setminus W^{*}$ and
$Y_{1}=Y\setminus W^{*}$. Clearly $|V(G_{1})|=2n-2|W|$ and
$\delta(G_{1})\geq(n+t/2)/2-|W|\geq(n-|W|)/2$. We show that
$G_{1}[X_{1},Y_{1}]$ satisfies Hall’s Condition. If not, we let $S\subseteq
X_{1}$ with smallest cardinality such that $|S|>|N_{G_{1}}(S)|$. By this
choice, $|S|=|N_{G_{1}}(S)|+1$ and $|N_{G_{1}}(S)|<|Y_{1}|$. As
$|S|>|N_{G_{1}}(S)|$, it follows that $|S|\geq\delta(G_{1})+1>(n-|W|)/2$ and
thus $|X_{1}\setminus S|=n-|W|-|S|<(n-|W|)/2$. Since $|N_{G_{1}}(S)|<|Y_{1}|$,
there exists $y\in Y_{1}\setminus N_{G_{1}}(S)$ such that
$N_{G_{1}}(y)\subseteq X_{1}\setminus S$. However, $d_{G_{1}}(y)\geq(n-|W|)/2$
but $|X_{1}\setminus S|<(n-|W|)/2$, we obtain a contradiction. Hence $G_{1}$
has a perfect matching $M_{2}$. Now $M_{1}\cup M_{2}$ is a perfect matching of
$G$. ∎

A path $P$ connecting two vertices $u$ and $v$ is called a $(u,v)$-path, and
we write $uPv$ or $vPu$ in specifying the two endvertices of $P$. Let $uPv$
and $xQy$ be two disjoint paths. If $vx$ is an edge, we write $uPvxQy$ as the
concatenation of $P$ and $Q$ through the edge $vx$. If $P$ is a path and
$x,y\in V(P)$, then $xPy$ is the subpath of $P$ with endvertices $x$ and $y$.

######  Lemma 2.12.

Let $0<1/n_{0}\ll\varepsilon<1$, and $G$ be graph on $2n\geq n_{0}$ vertices
such that $\delta(G)\geq(1+\varepsilon)n$. Moreover, let
$M=\\{a_{1}b_{1},\ldots,a_{t}b_{t}\\}$ be a matching in the complete graph on
$V(G)$ of size at most $\varepsilon n/4$. Then there exist vertex-disjoint
path $P_{1},\ldots,P_{t}$ in $G$ such that $\bigcup V(P_{i})=V(G)$ and $P_{i}$
joins $a_{i}$ to $b_{i}$, and these paths can be found in polynomial time.

Proof. For $i\in[1,t-1]$, $|N_{G}(a_{i})\cap N_{G}(b_{i})|\geq 2\varepsilon
n$, so we can greedily find vertices $c_{i}\in N_{G}(a_{i})\cap N_{G}(b_{i})$
such that $c_{i}\neq c_{j}$ for distinct $i,j\in[1,t-1]$. Thus we let
$P_{i}=a_{i}c_{i}b_{i}$. Let $G^{*}=G-\bigcup_{i=1}^{t-1}V(P_{i})$. Then
$\delta(G^{*})\geq(1+\varepsilon)n-3(t-1)\geq(1+\varepsilon/4)n$, and so
$G^{*}$ is hamiltonian-connected by Theorem 2.6. Thus we can find an
$(a_{t},b_{t})$-hamiltonian path $P_{t}$ in $G^{*}$.

It is clear that each of $P_{1},\ldots,P_{t-1}$ can be found in polynomial
time. For the path $P_{t}$, we construct it as below. By an algorithm
described in [16, Theorem 4], we can find a hamiltonian cycle $C$ of $G^{*}$.
By taking a longer segment between $a_{t}$ and $b_{t}$ from $C$, we get in
$G^{*}$ an $(a_{t},b_{t})$-path $Q_{1}$ that contains at least $|V(G^{*})|/2$
vertices. We will extend $Q_{1}$ into a hamiltonian $(a_{t},b_{t})$-path of
$G^{*}$. Denote by $Q_{2}$ the remaining segment of $C$ that is disjoint from
$Q_{1}$ and let $c$ and $d$ be the endvertices of $Q_{2}$. Let $|V(Q_{2})|=p$.
Then as $\delta(G^{*})\geq(1+\varepsilon/4)n$, each of $c$ and $d$ has on
$Q_{1}$ at least $(1+\varepsilon/4)n-(p-1)=(1+\varepsilon/4)n-p+1$ neighbors.
Since $2((1+\varepsilon/4)n-p)+p+|V(Q_{1})|>|V(G^{*})|$, it follows that one
of the following two situations must happen: (a) there is a vertex $c_{1}\in
N_{G^{*}}(c)\cap V(Q_{1})$ and a vertex $d_{1}\in N_{G^{*}}(d)\cap V(Q_{1})$
such that $c_{1}Q_{1}d_{1}$ contains less that $p+2$ vertices, and (b) $c$ or
$d$ has on $Q_{1}$ two neighbors that are consecutive on $Q_{1}$. When (a)
happens, assume by symmetry that $c_{1}$ is between $a_{t}$ and $d_{1}$ on
$Q_{1}$, then $Q_{1}^{*}=a_{t}Q_{1}c_{1}cQ_{2}dd_{1}Q_{1}b_{t}$ is longer than
$Q_{1}$ and the component of $G^{*}-V(Q_{1}^{*})$ still contains a hamiltonian
path. Similarly, we can extend $Q_{1}$ into a longer $(a_{t},b_{t})$-path such
that the subgraph of $G^{*}$ outside the path is hamiltonian if (b) happens.
Repeating this procedure at most $n$ times, we obtain a hamiltonian
$(a_{t},b_{t})$-path of $G^{*}$. Therefore, all the path $P_{1},\ldots,P_{t}$
can be found in polynomial time. ∎

##  3 Proof of Theorem 1.2

######  Theorem 1.2.

For all $0<\varepsilon<1$, there exists $n_{0}$ such that the following
statement holds: if $G$ is a graph on $2n\geq n_{0}$ vertices with
$\delta(G)\geq(1+\varepsilon)n$, then $\chi^{\prime}(G)=\Delta(G)$ if and only
if $G$ contains no $\Delta(G)$-overfull subgraph. Furthermore, there is a
polynomial time algorithm that finds an optimal coloring.

Proof. Choose constants $\varepsilon$ and positive integer $n_{0}$ such that
$0<1/n_{0}\ll\varepsilon$.

If $G$ is regular, then we are done by Theorem 1.3. Thus we assume that $G$ is
not regular. If $G$ contains a $\Delta(G)$-overfull subgraph, then
$\chi^{\prime}(G)=\Delta(G)+1$. Thus we assume that $G$ contains no
$\Delta(G)$-overfull subgraph. As a consequence,
$\operatorname{def}(G)\geq\Delta(G)$. By Lemma 2.10, we may assume that $G$
contains no $\Delta(G)$-full subgraph. Therefore, if two vertices with degree
less than $\Delta(G)$ are not adjacent in $G$, we may add the edge between
them without creating a $\Delta(G)$-overfull subgraph, or increasing
$\Delta(G)$. We iterate this edge-addition procedure. If at some point we
create a $\Delta(G)$-full subgraph, the result follows by Lemma 2.10.
Otherwise, we reach a point where we may now assume that in $G$ all vertices
with degree less than $\Delta(G)$ are mutually adjacent, and so by Lemma 2.7,
we have $|V_{\Delta}|\geq n+1$.

Define $n_{1}=|V_{\delta}|$. Note that $n_{1}<n$. If $n_{1}\geq n^{6/7}$ and
$\Delta(G)-\delta(G)\geq n^{6/7}$, then we are done by Theorem 1.3. Thus we
assume $n_{1}<n^{6/7}$ or $\Delta(G)-\delta(G)<n^{6/7}$, and we consider the
two cases below. We call a vertex of degree less than $\Delta(G)$ but greater
than $\delta(G)$ a _middle degree_ vertex.

Case 1. $n_{1}<n^{6/7}$.

Note that for any $v\in V(G)\setminus V_{\delta}$, $\delta(G-v-V_{\delta})\geq
n$ and so both $G-V_{\delta}$ and $G-v-V_{\delta}$ are hamiltonian by Theorem
2.6. Thus if $G-V_{\delta}$ and $G-v-V_{\delta}$ have even order, then they
each has a perfect matching. Hence if $n_{1}$ is even, we can decrease
$\Delta(G)-\delta(G)$ but preserve $\delta(G)$ in deleting a prefect matching
$M$ of $G-V_{\delta}$. If $n_{1}$ is odd but $G$ has a middle degree vertex
$v$, we can decrease $\Delta(G)-\delta(G)$ but preserve $\delta(G)$ in
deleting a prefect matching $M$ of $G-v-V_{\delta}$. Denote by $G_{1}$ the
reduced graph from $G$ by deleting $M$ in either of these two cases. If
$|V_{\delta}|\geq 2$, then as $V_{\delta}\subseteq V_{\delta}(G_{1})$, we know
that $G_{1}$ still contains no $\Delta(G_{1})$-overfull subgraph by Lemma 2.9.
Thus $|V_{\delta}|=1$. Let $V_{\delta}=\\{u\\}$. Note that $u\in
V_{\delta}(G_{1})$. Then
$\operatorname{def}(G_{1}-u)=d_{G}(u)+(\Delta(G_{1})-d_{G}(v))+\operatorname{def}_{G_{1}}(V(G_{1})\setminus\\{u,v\\})=d_{G}(u)+(\Delta(G)-1-d_{G}(v))+\operatorname{def}_{G}(V(G)\setminus\\{u,v\\})=\sum_{w\in
V(G-u)}(\Delta(G)-d_{G-u}(w))-1$. Since $G$ contains no $\Delta(G)$-overfull
subgraph, we have $\sum_{w\in V(G-u)}d_{G-u}(w)\geq\Delta(G)$. Thus
$\operatorname{def}(G_{1}-u)\geq\Delta(G)-1=\Delta(G_{1})$ and so $G_{1}$
contains no $\Delta(G_{1})$-overfull subgraph by Lemma 2.8. Furthermore,
$\chi^{\prime}(G_{1})=\Delta(G_{1})$ implies that
$\chi^{\prime}(G)=\Delta(G)$. Thus in these two cases, we can consider $G_{1}$
in place of $G$ and show that $G_{1}$ is a class 1 graph.

Thus we assume $n_{1}$ is odd and $G$ has no middle degree vertex. This in
particular, implies that $\delta(G)$ and $\Delta(G)$ have the same parity. As
$G$ has no $\Delta(G)$-overfull subgraph, $|V_{\delta}|\geq 3$. Let $x,y\in
V_{\delta}$ be distinct. We find a perfect matching $M_{11}$ in
$G-(V_{\delta}\setminus\\{x\\})$ and a perfect matching $M_{12}$ in
$G-(V_{\delta}\setminus\\{y\\})$. The matchings exist by Theorem 2.6. Let
$G_{1}=G-M_{11}-M_{12}$. We repeat this same process and find a perfect
matching $M_{21}$ in $G_{1}-(V_{\delta}\setminus\\{x\\})$ and a perfect
matching $M_{22}$ in $G_{1}-(V_{\delta}\setminus\\{y\\})$. For
$i\in[2,(\Delta(G)-\delta(G))/2]$, we let $G_{i}=G_{i-1}-M_{i1}-M_{i2}$. We
have $d_{G_{i}}(x)=d_{G_{i}}(y)=\delta(G)-i$. As $\Delta(G)-\delta(G)\leq
2n-(1+\varepsilon)n=(1-\varepsilon)n$, we see that
$d_{G_{i}}(x)=d_{G_{i}}(y)=\delta(G)-i\geq(1+\varepsilon)n-\frac{1}{2}(1-\varepsilon)n\geq(1+3\varepsilon/2)n$.
For any vertex $z\in V(G_{i})\setminus\\{x,y\\}$,
$d_{G_{i}}(z)\geq\delta(G)\geq(1+\varepsilon)n$. Let $x^{*}$ be a neighbor of
$x$ in $G_{i}-(V_{\delta}\setminus\\{x\\})$ and $y^{*}$ be a neighbor of $y$
in $G_{i}-(V_{\delta}\setminus\\{y\\})$. Then
$G_{i}-(V_{\delta}\setminus\\{x\\})-\\{x,x^{*}\\}$ has a prefect matching
$M_{(i+1)1}^{*}$, and $G_{i}-(V_{\delta}\setminus\\{y\\})-\\{y,y^{*}\\}$ has a
prefect matching $M_{(i+1)2}^{*}$. Let
$M_{(i+1)1}=M_{(i+1)1}^{*}\cup\\{xx^{*}\\}$ and
$M_{(i+1)2}=M_{(i+1)2}^{*}\cup\\{yy^{*}\\}$. Thus for each
$i\in[2,(\Delta(G)-\delta(G))/2]$, we find matchings $M_{i1}$ and $M_{i2}$
respectively from $G_{i-1}-(V_{\delta}\setminus\\{x\\})$ and
$G_{i-1}-(V_{\delta}\setminus\\{y\\})$.

We claim $G^{*}:=G_{(\Delta(G)-\delta(G))/2}$ satisfies Condition (b) of
Theorem 1.3. By the analysis above, we have
$d_{G^{*}}(x)=d_{G^{*}}(y)\geq(1/2+3\varepsilon/2)n$,
$d_{G^{*}}(z)=\Delta(G^{*})=\delta(G)\geq(1+\varepsilon)n$ for all $z\in
V(G^{*})\setminus\\{x,y\\}$. Also
$\Delta(G^{*})-\delta(G^{*})=\delta(G)-(\delta(G)-(\Delta(G)-\delta(G))/2)=\frac{1}{2}(\Delta(G)-\delta(G))\leq\frac{1}{2}(2n-(1+\varepsilon)n)=(1/2-\varepsilon/2)n$.
By Theorem 1.3, $\chi^{\prime}(G^{*})=\Delta(G^{*})=\delta(G)$. Taking an edge
$\delta(G)$-coloring of $G^{*}$, coloring edges $M_{i1}$ with color
$\delta(G)+2i-1$ and coloring edges $M_{i2}$ with color $\delta(G)+2i$ for
each $i\in[1,(\Delta(G)-\delta(G))/2]$, we obtain an edge $\Delta(G)$-coloring
of $G$.

Case 2. $\Delta(G)-\delta(G)<n^{6/7}$.

Let $V(G)=\\{x_{1},\ldots,x_{2n}\\}$ and we assume
$\operatorname{def}_{G}(x_{1})\geq\ldots\geq\operatorname{def}_{G}(x_{2n})=0$.
Since $x_{1}$ has the smallest degree in $G$ and $G-x_{1}$ is not
$\Delta(G)$-overfull by our assumption, $\sum_{i\geq
2}\operatorname{def}_{G}(x_{i})\geq\operatorname{def}_{G}(x_{1})$. Since
$|V(G)|=2n$ is even, $\sum_{i\geq 1}\operatorname{def}_{G}(x_{i})$ is even.
Then by Theorem 2.5, there exists a multigraph $H$ on $V(G)$ such that
$d_{H}(x)=\operatorname{def}_{G}(x_{i})$ for each $i\in[1,2n]$. This
multigraph $H$ will aid us to find a spanning regular subgraph of $G$.

Note that
$\Delta(H)=\operatorname{def}_{G}(x_{1})=\Delta(G)-\delta(G)<n^{6/7}$ and $H$
contains isolated vertices. Thus $\chi^{\prime}(H)\leq\Delta(H)+\mu(H)\leq
2\Delta(H)\leq 2n^{6/7}$. Hence we can greedily partition $E(H)$ into $k\leq
5n^{6/7}/\varepsilon$ matchings $M_{1},\ldots,M_{k}$ each of size at most
$\varepsilon n/5$. Now we take out linear forests from $G$ by applying Lemma
2.12 with $M_{1},\ldots,M_{k}$. More precisely, define spanning subgraphs
$G_{0},\ldots,G_{k}$ of $G$ and edge-disjoint linear forests
$F_{1},\ldots,F_{k}$ such that

  1. (1)

$G_{0}:=G$ and $G_{i}=G_{i-1}-E(F_{i})$ for $i\in[1,k]$,

  2. (2)

$F_{i}$ is a spanning linear forest (each vertex of $G_{i-1}$ has degree 1 or
2 in $F_{i}$) in $G_{i-1}$ whose leaves are precisely the vertices in $M_{i}$.

Let $G_{0}=G$ and suppose that for some $i\in[1,k]$, we already defined
$G_{0},\ldots,G_{i-1}$ and $F_{1},\ldots,F_{i-1}$. As
$\Delta(F_{1}\cup\ldots\cup F_{i-1})\leq 2(i-1)\leq 10n^{6/7}/\varepsilon$, it
follows that
$\delta(G_{i-1})\geq(1+\varepsilon)n-10n^{6/7}/\varepsilon\geq(1+4\varepsilon/5)n$.
Since $M_{i}$ has size at most $\varepsilon n/5$, we can apply Lemma 2.12 to
$G_{i-1}$ and $M_{i}$ and obtain a spanning linear forest $F_{i}$ in $G_{i-1}$
whose leaves are precisely the vertices in $M_{i}$. Set
$G_{i}:=G_{i-1}-E(F_{i})$.

We claim that $G_{k}$ is regular. Consider any vertex $u\in V(G_{k})$. For
every $i\in[1,k]$, $d_{F_{i}}(u)=1$ if $u$ is an endvertex of some edge of
$M_{i}$ and $d_{F_{i}}(u)=2$ otherwise. Since $M_{1},\ldots,M_{k}$ partition
$E(H)$, we know that
$\sum\limits_{i=1}^{k}d_{F_{i}}(u)=2k-d_{H}(u)=2k-\operatorname{def}_{G}(u)$.
Thus

$d_{G_{k}}(u)=d_{G}(u)-\sum\limits_{i=1}^{k}d_{F_{i}}(u)=d_{G}(u)-(2k-\operatorname{def}_{G}(u))=\Delta(G)-2k.$

Note that
$\Delta(G)\geq(1+\varepsilon)n-10n^{6/7}/\varepsilon\geq(1+4\varepsilon/5)n$.
Now $\chi^{\prime}(G_{k})=\Delta(G_{k})$ by Theorem 1.3. We color the edges of
$F_{i}$ using 2 distinct colors from $[\Delta(G)-2k+1,\Delta(G)]$ for each
$i\in[1,k]$. It is clear that any edge $\Delta(G_{k})$-coloring of $G_{k}$
together with this coloring of $\bigcup_{i=1}^{k}F_{i}$ gives an edge coloring
of $G$ using $\Delta(G_{k})+2k=\Delta(G)$ colors.

We lastly check that the procedure above yields a polynomial time algorithm.
Given $G$, taking a vertex $u$ of minimum degree in $G$. we first check if
$G-u$ is $\Delta(G)$-overfull. If yes, then $\chi^{\prime}(G)=\Delta(G)+1$ and
$G$ can be edge colored using $\Delta(G)+1$ colors in polynomial time [17].
Thus $G$ contains no $\Delta(G)$-overfull subgraph. If $G$ contains a
$\Delta(G)$-full subgraph, then an edge $\Delta(G)$-coloring of $G$ can be
found in polynomial time by Lemma 2.10. Thus $G$ contains no $\Delta(G)$-full
subgraph. If there exist nonadjacent $u,v\in V(G)\setminus V_{\Delta}$, we add
the edge $uv$ in $G$. If we reach a point where the resulting graph contains a
$\Delta(G)$-full subgraph, we then find an edge $\Delta(G)$-coloring of the
graph in polynomial time by Lemma 2.10, which also gives an edge
$\Delta(G)$-coloring of $G$. Thus we assume that every two vertices from
$V(G)\setminus V_{\Delta}$ are adjacent in $G$. If $G$ is Condition (c) of
Theorem 1.3, then we find an edge $\Delta(G)$-coloring of $G$ in polynomial
time by Theorem 1.3. Thus we have Case 1 or Case 2 as described in this proof.
If $G$ is in Case 1, it is polynomial time to find the desired matchings
(basically find hamiltonian cycles of even length in graphs with large minimum
degree by applying the algorithm described in [16, Theorem 4]) to reduce $G$
into a graph satisfying one of the conditions in Theorem 1.3. Then we find an
edge $\Delta(G)$-coloring of $G$ in polynomial time by Theorem 1.3. If $G$ is
in Case 2, then can construct an edge $\Delta(G)$-coloring of $G$ through the
process as described in Case 2. Since Theorem 2.5, Lemma 2.12 and Theorem 1.3
give appropriate running time statements, this can be achieved in time
polynomial in $n$. ∎

##  4 Proof of Theorem 1.3

The proofs in this section follow and extend ideas of Vaughan from [23], where
the techniques were for regular multigraphs but we modify them for graphs that
are not necessarily regular. We will need the following version of Chernoff
bound. (See e.g. [1, Theorem A.1.16].)

######  Lemma 4.1.

Let $X_{1},\ldots,X_{n}$ be mutually independent random variables that satisfy
$E(X_{i})=0$ and $|X_{i}|\leq 1$ for each $i\in[1,n]$. Set
$S=X_{1}+\ldots+X_{n}$. Then for any $a>0$,

$\operatorname{Pr}(|S|>a)<2e^{-a^{2}/2n}.$

######  Lemma 4.2 ([21], Lemma 3.2).

There exists a positive integer $n_{0}$ such that for all $n\geq n_{0}$ the
following holds. Let $G$ be a graph on $2n$ vertices, and
$N=\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}\subseteq V(G)$. Then $V(G)$ can be
partitioned into two parts $A$ and $B$ satisfying the properties below:

  1. (i)

$|A|=|B|$;

  2. (ii)

$|A\cap\\{x_{i},y_{i}\\}|=1$ for each $i\in[1,t]$;

  3. (iii)

$|d_{A}(v)-d_{B}(v)|\leq n^{2/3}-1$ for each $v\in V(G)$, where
$d_{S}(v)=|N_{G}(v)\cap S|$ for any $S\subseteq V(G)$.

Furthermore, one such partition can be constructed in
$O(2n^{3}\log_{2}(2n^{3}))$-time.

######  Theorem 1.3.

Let $0<1/n_{0}\ll\eta\ll\varepsilon<1$, and $G$ be a graph on $2n\geq n_{0}$
vertices. Assume that $G$ is in one of the following three conditions:

  1. (a)

$G$ regular with $\Delta(G)\geq(1+4\varepsilon/5)$n;

  2. (b)

$G$ has two distinct vertices $x,y$ such that
$d(x)=d(y)\geq(1/2+3\varepsilon/2)n$, and for all $z\in
V(G)\setminus\\{x,y\\}$, $d(z)=\Delta(G)\geq(1+\varepsilon)n$,
$\Delta(G)-\delta(G)\leq(1/2-\varepsilon/2)n$;

  3. (c)

$\Delta(G)-\delta(G)\geq n^{6/7}$, $|V_{\delta}|\geq n^{6/7}$ and
$|V_{\Delta}|\geq n+1$, and $\delta(G)\geq(1+\varepsilon)n$.

Then $\chi^{\prime}(G)=\Delta(G)$. Furthermore, there is a polynomial time
algorithm that finds an optimal coloring.

Proof. If $G$ is in Condition (a), we let $N=\emptyset$. If $G$ is in
Condition (b), we let $N=\\{x_{1},y_{1}\\}$ where $x_{1}=x$ and $y_{1}=y$. If
$G$ is in Condition (c), we take $2\lfloor(n-|V_{\Delta}|)/2\rfloor$ vertices
from $V(G)\setminus V_{\Delta}$ and name them as
$x_{1},y_{1},\ldots,x_{t},y_{t}$, where $t:=\lfloor(n-|V_{\Delta}|)/2\rfloor$
and we assume that the first $\lfloor|V_{\delta}|/2\rfloor$ pairs of vertices
$x_{i},y_{i}$ are all from $V_{\delta}$. Let
$N=\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}$. Applying Lemma 4.2 on $G$ and $N$,
we obtain a partition $\\{A,B\\}$ of $V(G)$ satisfying the following
properties:

  1. P.1

$|A|=|B|$;

  2. P.2

$|A\cap\\{x_{i},y_{i}\\}|=1$ for each $i\in[1,t]$;

  3. P.3

$|d_{A}(v)-d_{B}(v)|\leq n^{2/3}-1$ for each $v\in V(G)$.

Thus when $G$ is in Condition (b), we may assume $x\in A$ and $y\in B$. When
$G$ is in Condition (c), we know that $|A\cap
V_{\delta}|\geq\frac{1}{2}(|V_{\delta}|-1)$, $|B\cap
V_{\delta}|\geq\frac{1}{2}(|V_{\delta}|-1)$, $|A\cap V_{\Delta}|\geq n$ and
$|B\cap V_{\Delta}|\geq n$. By P.3, for any $v\in V(G)$, we have

$\frac{1}{2}\left(d_{G}(v)-n^{2/3}\right)\leq
d_{A}(v),d_{B}(v)\leq\frac{1}{2}\left(d_{G}(v)+n^{2/3}\right).$

Let

$G_{A}=G[A],\quad G_{B}=G[B],\quad\text{and }\quad H=G[A,B].$

To prove the theorem, we will construct an edge coloring of $G$ using
$\Delta(G)$ colors. We provide below an overview of the steps. At the start of
the process, $E(G)$ is assumed to be uncolored, and throughout the process,
the partial edge coloring of $G$ is always denoted by $\varphi$, which is
updating step by step.

  1. Step 1

Define $S=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq 7n^{2/3}\\}$. Let
$k=\max\\{\Delta(G_{A}),\Delta(G_{B})\\}+1$. By Theorem 2.1, we find an edge
$k$-coloring $\varphi$ of $G_{A}\cup G_{B}$. If there exist distinct $u,v\in
S\cap A$ or distinct $u,v\in S\cap B$ such that
$\overline{\varphi}(u)\cap\overline{\varphi}(v)\neq\emptyset$, we add an edge
joining $u$ and $v$ and color the new edge by a color in
$\overline{\varphi}(u)\cap\overline{\varphi}(v)$. The edge coloring $\varphi$
is updated and we still call it $\varphi$. We iterate this process of adding
and coloring edges and call the multigraphs resulting from $G_{A}$ and
$G_{B}$, respectively, $G^{*}_{A}$ and $G^{*}_{B}$, and call $G^{*}$ the union
of $G^{*}_{A}$, $G^{*}_{B}$ and $H$. We will modify the current edge coloring,
which is still named $\varphi$, such that the following properties are
satisfied:

    1. S1.1

When $G$ is in Conditions (a) or (b),

$|\overline{\varphi}^{-1}_{A}(i)|=|\overline{\varphi}^{-1}_{B}(i)|\quad\text{for
every $i\in[1,k]$}.$

When $G$ is in Condition (c), assume by symmetry that $e(G^{*}_{A})\leq
e(G^{*}_{B})$, then

$|\overline{\varphi}^{-1}_{A}(i)|\geq|\overline{\varphi}^{-1}_{B}(i)|\quad\text{for
every $i\in[1,k]$}.$

    2. S1.2

For every color $i\in[1,k]$,

(S1.I) $\begin{split}\sum\limits_{u\in
A}|\overline{\varphi}(u)|\leq\frac{n}{2}(n^{2/3}+1)+\frac{n}{2}(6n^{2/3})+k\leq
4n^{5/3}-2n,\\\ \sum\limits_{u\in
B}|\overline{\varphi}(u)|\leq\frac{n}{2}(n^{2/3}+1)+\frac{n}{2}(6n^{2/3})+k\leq
4n^{5/3}-2n,\\\ |\overline{\varphi}^{-1}_{A}(i)|\leq
4n^{2/3}\quad\text{and}\quad|\overline{\varphi}^{-1}_{B}(i)|\leq
4n^{2/3}.\end{split}$

  2. Step 2

Modify the partial edge-coloring of $G^{*}$ obtained in Step 1 by exchanging
alternating paths. When this step is finished, each of the $k$ color class
will be a 1-factor of $G^{*}$. During the process of this step, a few edges of
$H$ will be colored and a few edges of $G^{*}_{A}$ and $G^{*}_{B}$ will be
uncolored. Denote by $R_{A}$ and $R_{B}$, respectively, the submultigraphs of
$G^{*}_{A}$ and $G^{*}_{B}$ consisting of the uncolored edges. The two
multigraphs $R_{A}$ and $R_{B}$ will initially be empty, but one, two or three
edges will be added to at least one of them when each time we exchange an
alternating path. The conditions below will be satisfied at the completion of
this step:

    1. S2.1

The number of uncolored edges in each of $G_{A}^{*}$ and $G_{B}^{*}$ is less
than $12n^{5/3}$. When $G$ is in Conditions (a) or (b), $G_{A}^{*}$ and
$G_{B}^{*}$ have the same number of uncolored edges; and when $G$ is in
Condition (c), the number of uncolored edges in $G_{B}^{*}$ is greater than or
equal to the number of uncolored edges in $G_{A}^{*}$ (this follows from our
assumption that $e(G_{A}^{*})\leq e(G_{B}^{*})$).

    2. S2.2

$\Delta(R_{A})$ and $\Delta(R_{B})$ are less than $n^{5/6}+1.$

    3. S2.3

Define

$\displaystyle S_{A}$ $\displaystyle=$ $\displaystyle\\{u\in S\cap
A\,:\,d_{G_{A}^{*}}(u)\leq k-2n^{2/3}\\},$ $\displaystyle S_{B}$
$\displaystyle=$ $\displaystyle\\{u\in S\cap B\,:\,d_{G_{B}^{*}}(u)\leq
k-2n^{2/3}\\}.$

We require

      1. S2.3.1

Every vertex in $V(G^{*})\setminus(S_{A}\cup S_{B})$ is incident in $G^{*}$
with fewer than $2n^{5/6}$ colored edges of $H$.

      2. S2.3.2

When $G$ is in Condition (b), each of the vertex from $S_{A}\cup S_{B}$ is
incident in $G^{*}$ with fewer than $(\frac{1}{4}-\frac{1}{5}\varepsilon)n$
colored edges of $H$.

      3. S2.3.3

When $G$ is in Condition (c), each of the vertex from $S_{A}\cup S_{B}$ is
incident in $G^{*}$ with fewer than $(\frac{1}{2}-\frac{1}{3}\varepsilon)n$
colored edges of $H$.

  3. Step 3

We will edge color $R_{A}$ and $R_{B}$ and a few uncolored edges of $H$ using
another $\ell$ colors, where $\ell=\lceil 2n^{5/6}\rceil$. The goal is to
ensure that each of these $\ell$ new color classes obtained at the completion
of Step 3 presents at all vertices from $V(G^{*})\setminus V_{\delta}$ while
preserve the $k$ 1-factors already obtained through Steps 1 and 2.

  4. Step 4

At the start of Step 4, all of the uncolored edges of $G^{*}$ belong to $H$.
Denote by $R$ the subgraph of $G^{*}$ consisting of the uncolored edges. It
will be shown that $\Delta(R)=\Delta(G^{*})-k-\ell$. This subgraph is
bipartite, so we can color its edges using $\Delta(G^{*})-k-\ell$ colors by
Theorem 2.2.

When Step 4 is completed, we obtain an edge coloring of $G^{*}$ using exactly
$\Delta(G^{*})$ colors. We now give the details of each step, and for concepts
that were already defined in the outline above, we will use them directly.

Step 1: Coloring $G_{A}$ and $G_{B}$

Recall $S=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq 7n^{2/3}\\}$. Note that when
$G$ is in Condition (a), $S=\emptyset$; when $G$ is in Condition (b), then
$S\subseteq\\{x,y\\}$; and when $G$ is in Condition (c), then
$V_{\delta}\subseteq S$. Following the operations described in the outline of
Step 1, for the current edge coloring $\varphi$ of $G_{A}^{*}\cup G_{B}^{*}$,
the following statement holds:
$\overline{\varphi}(u)\cap\overline{\varphi}(v)=\emptyset$ for any two
distinct $u,v\in S\cap A$ or any two distinct $u,v\in S\cap B$. Therefore,

(S1.II) $\sum_{u\in A\cap S}|\overline{\varphi}(u)|=\sum_{u\in A\cap
S}\operatorname{def}_{G^{*}_{A}}(u)\leq k\quad\text{and}\quad\sum_{u\in B\cap
S}|\overline{\varphi}(u)|=\sum_{u\in B\cap
S}\operatorname{def}_{G^{*}_{B}}(u)\leq k.$

We will in the rest of the proof show that
$\chi^{\prime}(G^{*})=\Delta(G^{*})$, this is because $G$ is a subgraph of
$G^{*}$ and $\Delta(G^{*})=\Delta(G)$. The latter is seen as below: for any
$u\in S\cap A$, we have

$d_{G^{*}}(u)\leq
k+e_{G}(u,B)\leq\frac{1}{2}(\Delta(G)+n^{2/3})+1+\frac{1}{2}(\Delta(G)-7n^{2/3}+n^{2/3})\leq\Delta(G).$

Similarly, we have $d_{G^{*}}(u)\leq\Delta(G)$ for any $u\in S\cap B$. In
particular, if $u\in V_{\delta}$, as $\Delta(G)-\delta(G)\geq n^{6/7}$, we
have

(S1.III)
$d_{G^{*}}(u)\leq\frac{1}{2}(\Delta(G)+n^{2/3})+1+\frac{1}{2}(\Delta(G)-n^{6/7}+n^{2/3})\leq\Delta(G)-\frac{1}{3}n^{6/7}.$

Let $\varphi_{A}$ and $\varphi_{B}$ be the restrictions of $\varphi$ on
$G^{*}_{A}$ and $G^{*}_{B}$, respectively. By Lemma 2.3 and the comments
immediately below the lemma, we modify $\varphi_{A}$ and $\varphi_{B}$ into
equitable edge $k$-colorings of $G^{*}_{A}$ and $G^{*}_{B}$, respectively, and
still call $\varphi$ the edge $k$-coloring of $G^{*}_{A}\cup G^{*}_{B}$
consisting of the modifications of $\varphi_{A}$ and $\varphi_{B}$. Note that
under the new colorings, it is possible that
$\overline{\varphi}(u)\cap\overline{\varphi}(v)\neq\emptyset$ for some
distinct $u,v\in S\cap A$ or distinct $u,v\in S\cap B$. However the
inequalities in (S1.II) still hold.

When $G$ is in Conditions (a) or (b), we have $|S|\leq 2$ and
$e(G_{A})=e(G_{B})$ by the partition $\\{A,B\\}$ of $V(G)$. Since $|S\cap
A|=|S\cap B|\leq 1$, it follows that $G^{*}_{A}=G_{A}$ and $G^{*}_{B}=G_{B}$.
Thus $e(G^{*}_{A})=e(G^{*}_{B})$. Since $\varphi_{A}$ and $\varphi_{B}$ are
equitable edge $k$-colorings of $G^{*}_{A}$ and $G^{*}_{B}$, by renaming some
color names in $G^{*}_{A}$ if necessary, we assume

$|\overline{\varphi}^{-1}_{A}(i)|=|\overline{\varphi}^{-1}_{B}(i)|\quad\text{for
every $i\in[1,k]$}.$

When $G$ is in Condition (c), by symmetry, we assume $e(G^{*}_{A})\leq
e(G^{*}_{B})$. For the same reasoning as above, we assume

$|\overline{\varphi}^{-1}_{A}(i)|\geq|\overline{\varphi}^{-1}_{B}(i)|\quad\text{for
every $i\in[1,k]$}.$

By the Parity Lemma,
$|\overline{\varphi}^{-1}_{A}(i)|-|\overline{\varphi}^{-1}_{B}(i)|$ is even
for every $i\in[1,k]$. Therefore, we have the statement S1.1 as stated in the
outline of Step 1.

Next, we verify that every color $i\in[1,k]$ is missing at a small number of
vertices. Property P.2 of the partition $\\{A,B\\}$ implies $|A\cap
V_{\Delta}|\geq n/2$ and $|B\cap V_{\Delta}|\geq n/2$, and each vertex $u\in
V_{\Delta}$ satisfies $|\overline{\varphi}(u)|\leq n^{2/3}+1$, call this Fact
1. By the definition of $S$, for every $u\in V(G^{*})\setminus S$,
$d_{G^{*}}(u)=d_{G}(u)>\Delta(G^{*})-7n^{2/3}$, and Property P.3 of the
partition $\\{A,B\\}$ implies
$d_{G_{A}^{*}}(u)\geq\frac{1}{2}d_{G}(u)-n^{2/3}$ for every $u\in A\setminus
S$ and $d_{G_{B}^{*}}(u)\geq\frac{1}{2}d_{G}(u)-n^{2/3}$ for every $u\in
B\setminus S$. Thus $|\overline{\varphi}(u)|\leq
k-(\frac{1}{2}d_{G}(u)-n^{2/3})<6n^{2/3}$ for every $u\in V(G^{*})\setminus
S$, call this Fact 2. These two facts together with the fact in (S1.II), give

$\sum\limits_{u\in
A}|\overline{\varphi}(u)|\leq\frac{n}{2}(n^{2/3}+1)+\frac{n}{2}(6n^{2/3})+k\leq
4n^{5/3}-2n.$

Similarly,

$\sum\limits_{u\in
B}|\overline{\varphi}(u)|\leq\frac{n}{2}(n^{2/3}+1)+\frac{n}{2}(6n^{2/3})+k\leq
4n^{5/3}-2n.$

Since $\varphi_{A}$ and $\varphi_{B}$ are equitable edge $k$-colorings of
$G^{*}_{A}$ and $G^{*}_{B}$, we get

$|\overline{\varphi}^{-1}_{A}(i)|\leq
4n^{2/3}\quad\text{and}\quad|\overline{\varphi}^{-1}_{B}(i)|\leq 4n^{2/3}.$

Therefore, we have the statement S1.2 as stated in the outline of Step 1.

Step 2: Extending existing color classes into 1-factors

Each of the $k$ color classes obtained in Step 1 will be extended into $k$
1-factors of $G^{*}$ through exchanging of alternating paths, which consist of
colored edges and uncolored edges. The colored edges and uncolored edges of
these alternating paths are from $G^{*}_{A}\cup G^{*}_{B}$ and $H$,
respectively. Thus during the procedure of Step 2, we will uncolor some of the
edges of $G^{*}_{A}$ and $G^{*}_{B}$, and will color some of the edges of $H$.
Recall that $R_{A}$ and $R_{B}$ are the submultigraphs of $G^{*}_{A}$ and
$G^{*}_{B}$ consisting of the uncolored edges, which are empty initially.

To ensure Condition S2.2 is satisfied, we say that an edge $e=uv\in
E(G^{*}_{A}\cup G_{B}^{*})$ is _good_ if $e\not\in E(R_{A}\cup R_{B})$ and the
degree of $u$ and $v$ in both $R_{A}$ and $R_{B}$ is less than $n^{5/6}$
(actually, note that when $uv\in E(G_{A}^{*})$, then the degree of $u$ and $v$
is zero in $R_{B}$ and vice versa). Thus a good edge can be added to $R_{A}$
or $R_{B}$ without violating S2.2.

By S1.1, for each color $i\in[1,k]$, we pair up a vertex from
$\overline{\varphi}^{-1}_{B}(i)$ and a vertex from
$\overline{\varphi}^{-1}_{A}(i)$, and then pair up the remaining unpaired
vertices from $\overline{\varphi}^{-1}_{A}(i)$ as
$|\overline{\varphi}^{-1}_{A}(i)|-|\overline{\varphi}^{-1}_{B}(i)|$ is even
and we assumed
$|\overline{\varphi}^{-1}_{A}(i)|\geq|\overline{\varphi}^{-1}_{B}(i)|$. Each
of those pairs is called a _missing-common-color pair_ or _MCC-pair_ in short
with respect to the color $i$. In particular, when $G$ is in Conditions (a) or
(b), every vertex from $\overline{\varphi}^{-1}_{A}(i)$ is paired up with a
vertex from $\overline{\varphi}^{-1}_{B}(i)$.

For every MCC-pair $(a,b)$ with respect to some color $i\in[1,k]$, we will
exchange an alternating path $P$ from $a$ to $b$ with at most 11 edges, where,
if exist, the first, third, fifth, seventh, ninth, and eleventh edges are
uncolored and the second, fourth, sixth, eighth, and tenth edges are good
edges colored by $i$. After $P$ is exchanged, $a$ and $b$ will be incident
with edges colored by $i$, and at most three good edges will be added to each
of $R_{A}$ and $R_{B}$. With this information at hand, before demonstrating
the existence of such paths, we show that Conditions S2.1, S2.2 and S2.3 can
be guaranteed at the end of Step 2. After the completion of Step 1, by (S1.I),
the total number of missing colors from vertices in $A$ or from vertices in
$B$ is at most $4n^{5/3}-2n$. Thus there are at most $4n^{5/3}-2n$ MCC-pairs.
For each MCC-pair $(a,b)$ with $a,b\in V(G^{*})$, at most three edges will be
added to each of $R_{A}$ and $R_{B}$ when we exchange an alternating path from
$a$ to $b$. Thus there will always be fewer than

$3(4n^{5/3}-2n)<12n^{5/3}$

edges in each of $R_{A}$ and $R_{B}$. Thus Condition S2.1 will be satisfied at
the end of Step 2. And as we only ever add good edges to $R_{A}$ and $R_{B}$,
Condition S2.2 will hold automatically. We now show that Condition S2.3 will
also be satisfied. Recall

$S_{A}=\\{u\in S\cap A\,:\,d_{G_{A}^{*}}(u)\leq
k-2n^{2/3}\\}\quad\text{and}\quad S_{B}=\\{u\in S\cap
B\,:\,d_{G_{B}^{*}}(u)\leq k-2n^{2/3}\\}.$

Since $\sum_{u\in A\cap S}\operatorname{def}_{G^{*}_{A}}(u),\sum_{u\in B\cap
S}\operatorname{def}_{G^{*}_{B}}(u)\leq
k\leq\frac{1}{2}\Delta(G)+n^{2/3}+1<2n$, it follows that

$|S_{A}|<n^{1/3}\quad\text{and}\quad|S_{B}|<n^{1/3}.$

Thus for every vertex $u\in S\setminus(S_{A}\cup S_{B})$,
$|\overline{\varphi}(u)|<2n^{2/3}$. For every vertex $u\in V(G^{*})\setminus
S$, as $d_{G}(u)=d_{G^{*}}(u)>\Delta(G)-7n^{2/3}$, it follows that
$|\overline{\varphi}(u)|<k-(\frac{1}{2}(\Delta(G)-7n^{2/3})-n^{2/3})<6n^{2/3}$.
Thus for any $u\in V(G^{*})\setminus(S_{A}\cup S_{B})$, we have
$|\overline{\varphi}(u)|<6n^{2/3}$. In the process of Step 2, the number of
newly colored edges of $H$ that are incident with a vertex $u\in
V(G^{*})\setminus(S_{A}\cup S_{B})$ will equal the number of alternating paths
containing $u$ that have been exchanged. The number of such alternating paths
of which $u$ is the first vertex will equal the number of colors that missed
at $u$ at the end of Step 1, which is less than $6n^{2/3}$. The number of
alternating paths in which $u$ is not the first vertex will equal the degree
of $u$ in $R_{A}\cup R_{B}$, and so will be less than $n^{5/6}+1$. Hence the
number of colored edges of $H$ that are incident with $u$ will be less than

$6n^{2/3}+n^{5/6}+1<2n^{5/6}.$

This applies to all vertices in $V(G^{*})\setminus(S_{A}\cup S_{B})$, and so
Condition S2.3.1 will be satisfied.

When $G$ is in Condition (b), for any vertex $u\in S_{A}\cup S_{B}=\\{x,y\\}$,
since $\Delta(G)-\delta(G)\leq\frac{1}{2}(1-\varepsilon)n$, we have

$|\overline{\varphi}(u)|\leq k-\frac{1}{2}(d_{G}(u)-n^{2/3})\leq
k-\frac{1}{2}\left(\Delta(G)-\frac{1}{2}(1-\varepsilon)n-n^{2/3}\right)\leq\frac{1}{4}(1-\varepsilon)n+n^{2/3}+1.$

Hence the number of colored edges of $H$ that are incident with $u$ will be
less than

$\frac{1}{4}(1-\varepsilon)n+n^{2/3}+1+n^{5/6}+1<(\frac{1}{4}-\frac{1}{5}\varepsilon)n.$

Therefore, Condition S2.3.2 will be satisfied.

When $G$ is in Condition (c), for any vertex $u\in S_{A}\cup S_{B}$, since
$\Delta(G)-\delta(G)\leq(1-\varepsilon)n$, we have

$|\overline{\varphi}(u)|\leq k-\frac{1}{2}(d_{G}(u)-n^{2/3})\leq
k-\frac{1}{2}\left(\Delta(G)-(1-\varepsilon)n-n^{2/3}\right)\leq\frac{1}{2}(1-\varepsilon)n+n^{2/3}+1.$

Hence the number of colored edges of $H$ that are incident with $u$ will be
less than

$\frac{1}{2}(1-\varepsilon)n+n^{2/3}+1+n^{5/6}+1<(\frac{1}{2}-\frac{1}{3}\varepsilon)n.$

Therefore, Condition S2.3.3 will be satisfied.

We now show below the existence of alternating paths for MCC-pairs. For a
given color $i\in[1,k]$, and vertices $a\in A$ and $b\in B$, let $N_{B}(a)$ be
the set of vertices in $B$ that are joined with $a$ by an uncolored edge and
are incident with a good edge colored $i$ such that the good edge is not
incident with any vertex of $S_{B}$, and let $N_{A}(b)$ be the set of vertices
in $A$ that are joined with $b$ by an uncolored edge and are incident with a
good edge colored $i$ such that the good edge is not incident with any vertex
of $S_{A}$. In order to estimate the sizes of $N_{A}(b)$ and $N_{B}(b)$, we
show that $A$ and $B$ contains only a few vertices that either miss the color
$i$ or are incident with a non-good edge colored $i$. By S2.1, there are at
most $12n^{5/3}$ edges in $R_{B}$, so there are fewer than $24n^{5/6}$
vertices of degree at least $n^{5/6}$ in $R_{B}$. Each non-good edge is
incident with one or two vertices of $R_{B}$ through the color $i$, so there
are fewer than $48n^{5/6}$ vertices in $B$ that are incident with a non-good
edge colored $i$. Furthermore, there are at most $2|S_{B}|\leq 2n^{1/3}$
vertices in $B$ that are either contained in $S_{B}$ or adjacent to a vertex
from $S_{B}$ through an edge with color $i$. Finally, there are fewer than
$4n^{2/3}$ vertices in $B$ that are missed by the color $i$. So the number of
vertices in $B$ that are not incident with a good edge colored $i$ such that
the good edge is not incident with any vertex from $S_{B}$ is less than

$48n^{5/6}+2n^{1/3}+4n^{2/3}<49n^{5/6}.$

By symmetry, the number of vertices in $A$ that are not incident with a good
edge colored $i$ such that the good edge is not incident with any vertex from
$S_{A}$ is less than $49n^{5/6}$. By S2.3.1, when $\\{a,b\\}\cap(S_{A}\cup
S_{B})=\emptyset$,

(S2.I)
$|N_{A}(b)|,|N_{B}(a)|\geq\frac{1}{2}\left((1+4\varepsilon/5)n-n^{2/3}\right)-2n^{5/6}-49n^{5/6}>(\frac{1}{2}+\frac{1}{3}\varepsilon)n.$

When $G$ is in Condition (b) and $\\{a,b\\}\cap\\{x,y\\}\neq\emptyset$, by
S2.3.2, we have

(S2.II)
$|N_{A}(b)|,|N_{B}(a)|\geq\frac{1}{2}\left((1/2+3\varepsilon/2)n-n^{2/3}\right)-(\frac{1}{4}-\frac{1}{5}\varepsilon)n-49n^{5/6}>\frac{3}{4}\varepsilon
n.$

When $G$ is in Condition (c) and $\\{a,b\\}\cap(S_{A}\cup
S_{B})\neq\emptyset$, by S2.3.3, we have

(S2.III)
$|N_{A}(b)|,|N_{B}(a)|\geq\frac{1}{2}\left((1+\varepsilon)n-n^{2/3}\right)-(\frac{1}{2}-\frac{1}{3}\varepsilon)n-49n^{5/6}>\frac{1}{2}\varepsilon
n.$

Let $M_{B}(a)$ be the set of vertices in $B$ that are joined with a vertex in
$N_{B}(a)$ by an edge of color $i$, and let $M_{A}(b)$ be the set of vertices
in $A$ that are joined with a vertex in $N_{A}(b)$ by an edge of color $i$.
Note that $(S_{A}\cup S_{B})\cap(M_{A}(b)\cup M_{B}(a))=\emptyset$ by the
choice of $N_{A}(b)$ and $N_{B}(a)$. Note also that $|M_{B}(a)|=|N_{B}(a)|$
but some vertices may be in both. Similarly $|M_{A}(b)|=|N_{A}(b)|$.

For a MCC-pair $(a,b)$, in order to have a uniform discussion as in the case
that $\\{a,b\\}\cap(S_{A}\cup S_{B})=\emptyset$, if necessary, by exchanging
an alternating path of length 2 from $a$ to another vertex $a^{*}$, and
exchanging an alternating path from $b$ to another vertex $b^{*}$, we will
replace the pair $(a,b)$ by $(a^{*},b^{*})$ such that
$\\{a^{*},b^{*}\\}\cap(S_{A}\cup S_{B})=\emptyset$. Precisely, we will
implement the following operations to vertices in $S_{A}\cup S_{B}$. For any
vertex $a\in S_{A}$, and for each color $i\in\overline{\varphi}(a)$, we take
an edge $b_{1}b_{2}$ with $b_{1}\in N_{B}(a)$ and $b_{2}\in M_{B}(a)$ such
that $b_{1}b_{2}$ is colored by $i$, where the edge $b_{1}b_{2}$ exists by
(S2.II)-(S2.III) and the fact that $|M_{B}(a)|=|N_{B}(a)|$. Then we exchange
the path $ab_{1}b_{2}$ by coloring $ab_{1}$ with $i$ and uncoloring the edge
$b_{1}b_{2}$ (See Figure 1 (a)). After this, the edge $ab_{1}$ of $H$ is now
colored by $i$, and the uncolored edge $b_{1}b_{2}$ is added to $R_{B}$. We
then update the original MCC-pair that contains $a$ with respect to the color
$i$ by replacing the vertex $a$ with $b_{2}$. We do this at the vertex $a$ for
every color $i\in\overline{\varphi}(a)$ and then repeat the same process for
every vertex in $S_{A}$. Similarly, for any vertex $b\in S_{B}$, and for each
color $i\in\overline{\varphi}(b)$, we take an edge $a_{1}a_{2}$ with $a_{1}\in
N_{A}(b)$ and $a_{2}\in M_{A}(b)$ such that $a_{1}a_{2}$ is colored by $i$,
where the edge $a_{1}a_{2}$ exists by (S2.II)-(S2.III) and the fact that
$|M_{B}(b)|=|N_{B}(b)|$. Then we exchange the path $ba_{1}a_{2}$ by coloring
$ba_{1}$ with $i$ and uncoloring the edge $a_{1}a_{2}$. The same, we update
the original MCC-pair that contains $b$ with respect to the color $i$ by
replacing the vertex $b$ with $a_{2}$.

After the procedure above, we have now three types MCC-pair $(u,v)$: $u,v\in
A$, $u,v\in B$, and $A$ contains exactly one of $u$ and $v$ and $B$ contains
the other. However, in either case, $\\{u,v\\}\cap(S_{A}\cup
S_{B})=\emptyset$. We will exchange alternating path for each of such pairs.

We deal with each of the colors from $[1,k]$ in turn. Let $i\in[1,k]$ be a
color. We consider first an MCC-pair $(a,a^{*})$ with respect to $i$ such that
$a,a^{*}\in A$. By (S2.I), we have
$|M_{B}(a^{*})|>(\frac{1}{2}+\frac{1}{3}\varepsilon)n$. We take an edge
$b_{1}^{*}b_{2}^{*}$ colored by $i$ with $b_{1}^{*}\in N_{B}(a^{*})$ and
$b_{2}^{*}\in M_{B}(a^{*})$. Then again, by (S2.I), we have
$|M_{B}(a)|,|M_{A}(b_{2}^{*})|>(\frac{1}{2}+\frac{1}{3}\varepsilon)n.$
Therefore, as each vertex $c\in M_{A}(b_{2}^{*})$ satisfies
$|N_{B}(c)|>(\frac{1}{2}+\frac{1}{3}\varepsilon)n$, we have $|N_{B}(c)\cap
M_{B}(a)|\geq\frac{2}{3}\varepsilon n$. We take $a_{2}a_{2}^{*}$ colored by
$i$ with $a_{2}^{*}\in N_{A}(b_{2}^{*})$ and $a_{2}\in M_{A}(b_{2}^{*})$. Then
we let $b_{2}\in N_{B}(a_{2})\cap M_{B}(a)$, and let $b_{1}$ be the vertex in
$N_{B}(a)$ such that $b_{1}b_{2}$ is colored by $i$. Now we get the
alternating path $P=ab_{1}b_{2}a_{2}a_{2}^{*}b_{2}^{*}b_{1}^{*}a^{*}$ (See
Figure 1 (c)). We exchange $P$ by coloring
$ab_{1},b_{2}a_{2},a_{2}^{*}b_{2}^{*}$ and $b_{1}^{*}a^{*}$ with color $i$ and
uncoloring the edges $b_{1}b_{2},b_{1}^{*}b_{2}^{*}$ and $a_{2}a_{2}^{*}$.
After the exchange, the color $i$ appears on edges incident with $a$ and
$a^{*}$, the edges $b_{1}b_{2}$ and $b_{1}^{*}b_{2}^{*}$ are added to $R_{B}$
and the edge $a_{2}a_{2}^{*}$ is added to $R_{A}$. We added at most one edge
to each of $R_{A}$ and $R_{B}$ when we updated the original MCC-pair
corresponding to $(a,a^{*})$. Thus we added at most three edges to each of
$R_{A}$ and $R_{B}$ when we modify $\varphi$ to have the color $i$ present at
both of the vertices in the original MCC-pair corresponding to $(a,a^{*})$. By
symmetry, we can deal with an MCC-pair $(b,b^{*})$ with respect to $i$ such
that $b,b^{*}\in B$ similarly as above.

Thus we consider an MCC-pair $(a,b)$ with respect to $i$ such that $a\in A$
and $b\in B$. By (S2.I), we have
$|M_{B}(a)|,|M_{A}(b)|>(\frac{1}{2}+\frac{1}{3}\varepsilon)n.$ We choose
$a_{1}a_{2}$ with color $i$ such that $a_{1}\in N_{A}(b)$ and $a_{2}\in
M_{A}(b)$. Now as
$|M_{B}(a)|,|N_{B}(a_{2})|>(\frac{1}{2}+\frac{1}{3}\varepsilon)n$ by (S2.I),
we know that $N_{B}(a_{2})\cap M_{B}(a)\neq\emptyset$. We choose $b_{2}\in
N_{B}(a_{2})\cap M_{B}(a)$ and let $b_{1}\in N_{B}(a)$ such that $b_{1}b_{2}$
is colored by $i$. Then $P=ab_{1}b_{2}a_{2}a_{1}b$ is an alternating path from
$a$ to $b$ (See Figure 1 (b)). We exchange $P$ by coloring $ab_{1},b_{2}a_{2}$
and $a_{1}b$ with color $i$ and uncoloring the edges $a_{1}a_{2}$ and
$b_{1}b_{2}$. After the exchange, the color $i$ appears on edges incident with
$a$ and $b$, the edge $a_{1}a_{2}$ is added to $R_{A}$ and the edge
$b_{1}b_{2}$ is added to $R_{B}$. We added at most one edge to each of $R_{A}$
and $R_{B}$ when we updated the original MCC-pair corresponding to $(a,b)$.
Thus we added at most three edges to each of $R_{A}$ and $R_{B}$ when we
modify $\varphi$ to have the color $i$ present at both of the vertices in the
original MCC-pair corresponding to $(a,b)$. By finding such paths for all MCC-
pairs with respect to the color $i$, we can increase the number of edges
colored $i$ until the color class is a 1-factor of $G^{*}$. By doing this for
all colors, we can make each of the $k$ color classes a 1-factor of $G^{*}$.

$a$$b_{1}$$b_{2}$$A$$B$$(a)$$a$$a_{1}$$a_{2}$$b$$b_{1}$$b_{2}$$A$$B$$(b)$$a$$a_{2}$$a^{*}_{2}$$a^{*}$$b_{1}$$b_{2}$$b^{*}_{2}$$b^{*}_{1}$$A$$B$$(c)$

-

Figure 1: The alternating path $P$. Dashed lines indicate uncoloured edges,
and solid lines indicate edges with color $i$.

Step 3: Coloring $R_{A}$ and $R_{B}$ and extending the new color classes

Each of the color classes for the colors from $[1,k]$ is now a 1-factor of
$G^{*}$. We now consider the multigraphs $R_{A}$ and $R_{B}$ that consist of
the uncolored edges of $G^{*}_{A}$ and $G^{*}_{B}$. By Condition S2.1, $R_{A}$
and $R_{B}$ each has fewer than $12n^{5/3}$ edges, and
$\Delta(R_{A}),\Delta(R_{B})<n^{5/6}+1$. Note that $R_{A}$ and $R_{B}$ might
contain parallel edges with endvertices in $S$. By Theorem 2.1 and Theorem
2.3, $R_{A}$ and $R_{B}$ each has an equalized edge-coloring with exactly
$\ell:=\lceil 2n^{5/6}\rceil$ colors $k+1,\ldots,k+\ell$.

If $G$ is in Conditions (a) or (b), then we have $e(R_{A})=e(R_{B})$. Under
these two conditions, by renaming some color classes of $R_{A}$ if necessary,
we can assume that in the edge colorings of $R_{A}$ and $R_{B}$, each color
appears on the same number of edges in $R_{A}$ as it does in $R_{B}$. When $G$
is in Condition (c), by our assumption that $G^{*}_{B}$ has more edges than
$G^{*}_{A}$ does, we have $e(R_{A})\leq e(R_{B})$. In this case, we can assume
that in the edge colorings of $R_{A}$ and $R_{B}$, the number of edges with a
color $i\in[k+1,k+\ell]$ in $R_{B}$ is at least the number of edges with a
color $i\in[k+1,k+\ell]$ in $R_{A}$.

There are fewer than $12n^{5/3}$ edges in each of $R_{A}$ and $R_{B}$, and
$\ell>n^{5/6}$, so each of the color $i\in[k+1,k+\ell]$ appears on fewer than
$12n^{5/6}+1$ edges in each of $R_{A}$ and $R_{B}$. We will now color some of
the edges of $H$ with the $\ell$ colors from $[k+1,k+\ell]$ so that each of
these color classes present at vertices from $V(G^{*})\setminus V_{\delta}$.
We perform the following procedure for each of the $\ell$ colors in turn.

Given a color $i$ with $i\in[k+1,k+\ell]$, we let $A_{i}$ and $B_{i}$ be the
sets of vertices in $A$ and $B$ respectively that are incident with edges
colored $i$. Note that $|A_{i}|\leq|B_{i}|<2(12n^{5/6}+1)$ as $R_{A}$ and
$R_{B}$ each contains fewer than $12n^{5/6}+1$ edges colored $i$. Note that if
$G$ is in Conditions (a) or (b), we have $|A_{i}|=|B_{i}|$; and we might have
$|B_{i}|\geq|A_{i}|$ when $G$ is in Condition (c). When $G$ is in Condition
(c) and $|B_{i}|>|A_{i}|$, we let

$A_{i}^{*}\subseteq(V_{\delta}\cap A)\setminus A_{i}$

such that $|A_{i}^{*}|+|A_{i}|=|B_{i}|$, and just let $A_{i}^{*}=\emptyset$
otherwise. Note that such $A_{i}^{*}$ exists as $|V_{\delta}\cap
A|\geq\frac{1}{2}n^{6/7}-1$ and $|A_{i}|,|B_{i}|<2(12n^{5/6}+1)$. Let $H_{i}$
be the subgraph of $H$ obtained by deleting the vertex sets $A_{i}\cup
A_{i}^{*}$ and $B_{i}$ and removing all colored edges. We will show next that
$H_{i}$ has a perfect matching and we will color the edges in the matching by
the color $i$.

Each vertex in $V(G^{*})\setminus(S_{A}\cup S_{B})$ is incident with fewer
than $2n^{5/6}+\ell\leq 5n^{5/6}$ edges of $H$ that are coloured, since fewer
than $2n^{5/6}$ were colored in Step 2 by S2.3.1 and at most
$2n^{5/6}+2<3n^{5/6}$ have been colored in Step 3. Also each vertex in $G^{*}$
has fewer than $2(12n^{5/6}+1)$ edges that join it with a vertex in $A_{i}$ or
$B_{i}$. So each vertex from $V(H_{i})\setminus(S_{A}\cup S_{B})$ is adjacent
in $H_{i}$ to more than

$\frac{1}{2}\left((1+4\varepsilon/5)n-n^{2/3}\right)-5n^{5/6}-2(12n^{5/6}+1)>\frac{1}{2}(1+\varepsilon/2)n$

vertices.

When $G$ is in condition (b), each vertex in $S_{A}\cup S_{B}$ is incident
with fewer than $(\frac{1}{4}-\frac{1}{5}\varepsilon)n+3n^{5/6}$ edges of $H$
that are coloured, since fewer than $(\frac{1}{4}-\frac{1}{5}\varepsilon)n$
were colored in Step 2 by S2.3.2 and at most $3n^{5/6}$ have been colored in
Step 3. Also each vertex in $G^{*}$ has fewer than $2(12n^{5/6}+1)$ edges that
join it with a vertex in $A_{i}$ or $B_{i}$. So when $G$ is in Condition (b),
each vertex from $S_{A}\cup S_{B}$ is adjacent in $H_{i}$ to more than

$\frac{1}{2}\left((1/2+3\varepsilon/2)n-n^{2/3}\right)-\left((\frac{1}{4}-\frac{1}{5}\varepsilon)n+3n^{5/6}\right)-2(12n^{5/6}+1)>\frac{3}{4}\varepsilon
n$

vertices.

When $G$ is in condition (c), each vertex in $S_{A}\cup S_{B}$ is incident
with fewer than $(\frac{1}{2}-\frac{1}{3}\varepsilon)n+3n^{5/6}$ edges of $H$
that are coloured, since fewer than $(\frac{1}{2}-\frac{1}{3}\varepsilon)n$
were colored in Step 2 by S2.3.3 and at most $3n^{5/6}$ have been colored in
Step 3. Also each vertex in $G^{*}$ has fewer than $2(12n^{5/6}+1)$ edges that
join it with a vertex in $A_{i}\cup A_{i}^{*}$ or $B_{i}$. So when $G$ is in
Condition (c), each vertex from $S_{A}\cup S_{B}$ is adjacent in $H_{i}$ to
more than

$\frac{1}{2}\left((1+\varepsilon)n-n^{2/3}\right)-\left((\frac{1}{2}-\frac{1}{3}\varepsilon)n+3n^{5/6}\right)-2(12n^{5/6}+1)>\frac{1}{2}\varepsilon
n$

vertices.

Thus $\delta(H_{i})\geq\frac{1}{2}\varepsilon n$ in either case and $H_{i}$
has at most $|S_{A}\cup S_{B}|\leq 2n^{1/3}<\frac{1}{2}\varepsilon n$ vertices
of degree less than $\frac{1}{2}(1+\varepsilon/2)n$. So $H_{i}$ has a 1-factor
$F$ by Lemma 2.11. If we color the edges of $F$ with the color $i$, then every
vertex in $V(G^{*})\setminus A_{i}^{*}$ is incident with an edge of color $i$.
We repeat this procedure for each of the colors from $[k+1,k+\ell]$. After
this has been done, each of these $\ell$ colors presents at all vertices from
$V(G^{*})\setminus V_{\delta}$. So at the conclusion of Step 3, all of the
edges in $G^{*}_{A}$ and $G^{*}_{B}$ are colored, some of the edges of $H$ are
colored, each of the $k$ color classes for colors from $[1,k]$ is a 1-factor
of $G^{*}$, and each of the $\ell$ colors from $[k+1,k+\ell]$ presents at all
vertices from $V(G^{*})\setminus V_{\delta}$.

Step 4: Coloring the graph $R$

Let $R$ be the subgraph of $G^{*}$ consisting of the remaining uncolored
edges. These edges all belong to $H$, so $R$ is a subgraph of $H$ and hence is
bipartite. We claim that $\Delta(R)=\Delta(G^{*})-k-\ell$. Note that every
vertex from $V(G^{*})\setminus V_{\delta}$ presents every color from
$[1,k+\ell]$ and so those vertices have degree exactly $\Delta(G^{*})-k-\ell$
in $R$. For some vertices from $V_{\delta}$, they present all the colors from
$[1,k]$. Thus by (S1.III), those vertices have degree at most

$\Delta(G^{*})-\frac{1}{3}n^{6/7}-k<\Delta(G^{*})-k-\ell$

in $R$. By Theorem 2.2 we can color the edges of $R$ with $\Delta(R)$ colors
from $[k+\ell+1,\Delta(G^{*})]$. Thus $\chi^{\prime}(G^{*})\leq
k+\ell+(\Delta(G^{*})-k-\ell)=\Delta(G^{*})$ and so
$\chi^{\prime}(G^{*})=\Delta(G^{*})$, as desired.

Lastly, we check that there is a polynomial time algorithm to obtain an edge
$\Delta(G)$-coloring of $G$. By Lemma 4.2, we can obtain a desired partition
$\\{A,B\\}$ of $V(G)$ in polynomial time. Also, it is polynomial time to edge
color $G_{A}$ and $G_{B}$ by an algorithm described in [17]. Modifying $G_{A}$
and $G_{B}$ into $G_{A}^{*}$ and $G_{B}^{*}$ and the corresponding edge
colorings into equalized edge-colorings can be done in polynomial time too. In
Step 2, the construction of the alternating paths and swaps of the colors on
the paths can be done in $O(n^{3})$-time, as the total number of colors
missing at vertices is $O(n^{2})$ and it takes $O(n)$-time to find an
alternating path for a MCC-pair. In Step 3, there is polynomial time algorithm
(see e.g. [13]) to edge color $R_{A}$ and $R_{B}$ using at most $\ell$ colors.
Then by doing Kempe changes as mentioned in the comments immediately after
Theorem 2.3, these edge colorings can be modified into equalized edge-
colorings in polynomial time. The last step is to edge color the bipartite
graph $R$ using $\Delta(R)$ colors, which cab be done in polynomial-time in
$n$, for example, using an algorithm from [4]. Thus, there is a polynomial
time algorithm that gives an edge coloring of $G$ using $\Delta(G)$ colors. ∎

## References

  * [1] N. Alon and J. H. Spencer.  The probabilistic method.  Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, third edition, 2008.  With an appendix on the life and work of Paul Erdős.
  * [2] 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.
  * [3] 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.
  * [4] R. Cole and J. Hopcroft.  On edge coloring bipartite graphs.  SIAM J. Comput., 11(3):540–546, 1982.
  * [5] 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.
  * [6] G. A. Dirac.  Some theorems on abstract graphs.  Proc. London Math. Soc. (3), 2:69–81, 1952.
  * [7] S. Fiorini and R. J. Wilson.  Edge-colourings of graphs, Research notes in Maths.  Pitman, London, 1977.
  * [8] S. Glock, D. Kühn, and D. Osthus.  Optimal path and cycle decompositions of dense quasirandom graphs.  J. Combin. Theory Ser. B, 118:88–108, 2016.
  * [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] S. L. Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph. I.  J. Soc. Indust. Appl. Math., 10:496–506, 1962.
  * [12] I. Holyer.  The NP-completeness of edge-coloring.  SIAM J. Comput., 10(4):718–720, 1981.
  * [13] H. J. Karloff and D. B. Shmoys.  Efficient parallel algorithms for edge coloring problems.  J. Algorithms, 8(1):39–52, 1987.
  * [14] D. König.  Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.  Math. Ann., 77(4):453–465, 1916.
  * [15] C. J. H. McDiarmid.  The solution of a timetabling problem.  J. Inst. Math. Appl., 9:23–34, 1972.
  * [16] C. McDiarmid and N. Yolov.  Hamilton cycles, minimum degree, and bipartite holes.  Journal of Graph Theory, 86(3):277–285, 2017.
  * [17] J. Misra and D. Gries.  A constructive proof of Vizing’s theorem.  Inform. Process. Lett., 41(3):131–133, 1992.
  * [18] T. Niessen.  How to find overfull subgraphs in graphs with large maximum degree. II.  Electron. J. Combin., 8(1):Research Paper 7, 11, 2001.
  * [19] M. Plantholt.  Overfull conjecture for graphs with high minimum degree.  J. Graph Theory, 47(2):73–80, 2004.
  * [20] P. D. Seymour.  On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.  Proc. London Math. Soc. (3), 38(3):423–460, 1979.
  * [21] S. Shan.  Chromatic index of dense quasirandom graphs.  arXiv:2104.06253, 2021.
  * [22] 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.
  * [23] E. R. Vaughan.  An asymptotic version of the multigraph 1-factorization conjecture.  J. Graph Theory, 72(1):19–29, 2013.
  * [24] V. G. Vizing.  Critical graphs with given chromatic class.  Diskret. Analiz No., 5:9–17, 1965.