# The overfull conjecture on graphs of odd order and large minimum degree

Songling Shan
Illinois State University, Normal, IL 61790
<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\frac{1}{2}|V(H)|\rfloor$. Chetwynd and Hilton in 1986
conjectured that a graph $G$ with $\Delta(G)>\frac{1}{3}|V(G)|$ has chromatic
index $\Delta(G)$ if and only if $G$ contains no overfull subgraph. Let
$0<\varepsilon<1$ and $G$ be a large graph on $n$ vertices with minimum degree
at least $\frac{1}{2}(1+\varepsilon)n$. It was shown that the conjecture holds
for $G$ if $n$ is even. In this paper, the same result is proved if $n$ is
odd. As far as we know, this is the first result on the conjecture for graphs
of odd order and with a minimum degree constraint.

_Keywords._ Chromatic index; 1-factorization; Overfull Conjecture; Overfull
graph.

##  1 Introduction

In this paper, the terminology graph is used to represent a simple graph. A
multigraph may contain multiple edges but contains no loop. Let $G$ be a
multigraph. We use $V(G)$ and $E(G)$ to denote the vertex set and the edge set
of $G$, respectively, and let $e(G)=|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$. We let
$d_{G}^{s}(v)=|N_{G}(v)|$, and call it the _simple degree_ of $v$ in $G$. When
$G$ is simple, we have $d_{G}(v)=d_{G}^{s}(v)$. 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. We also use
$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 $S\subseteq V(G)$ and
$v\in V(G)$, $N_{G}(v,S):=N_{G}(v)\cap S$ and
$d_{S}(v):=e_{G}(v,S\setminus\\{v\\})$, the subgraph of $G$ induced by $S$ is
$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
$\mu(G)=\max\\{e_{G}(u,v)\,:\,u,v\in V(G)\\}$ be the multiplicity of $G$, and
for $x\in V(G)$, let $\mu(x)=\max\\{e_{G}(x,v):v\in V(G)\\}$ be the
multiplicity of $x$.

For two integers $p,q$, let $[p,q]=\\{i\in\mathbb{Z}\,:\,p\leq i\leq q\\}$.
For a nonnegative integer $k$, 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 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 [25] showed that for all
graphs $G$, $\Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1$. This leads to a
natural classification of graphs. Following Fiorini and Wilson [8], 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. However, there are
sufficient conditions for a graph to be class 2. For example, any graph $G$
with $|E(G)|>\Delta(G)\lfloor|V(G)|/2\rfloor$ is class 2, since each color
class of $G$ is a matching and each matching in $G$ has size at most
$\lfloor|V(G)|/2\rfloor$, we have
$\chi^{\prime}(G)\geq|E(G)|/\lfloor|V(G)|/2\rfloor>\Delta(G)$ but
$\chi^{\prime}(G)\leq\Delta(G)+1$ by the result of Gupta and Vizing. Such
graphs $G$ are called _overfull_ (we can define a multigraph to be overfull in
the same way). 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 [24] lie in
deciding when a graph is overfull. Chetwynd and Hilton [3, 4], in 1986,
proposed the following conjecture.

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

Let $G$ be a 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, has $\chi^{\prime}(P^{*})=4$, 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
[22] 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)|$. There have been some fairly strong results
supporting the Overfull Conjecture in the case when $G$ is regular. It is easy
to verify that when $G$ is regular with even order, $G$ has no
$\Delta(G)$-overfull subgraphs if its vertex degrees are at least
$\frac{1}{2}|V(G)|$. Thus the well-known 1-Factorization Conjecture stated
below is a special case of the Overfull Conjecture.

######  Conjecture 1.2 (1-Factorization Conjecture).

Let $G$ be a regular graph of order $2n$ with degree at least $n$ if $n$ is
odd, or at least $n-1$ if $n$ is even. Then $G$ is 1-factorable; equivalently,
$\chi^{\prime}(G)=\Delta(G)$.

Hilton and Chetwynd [2] verified the 1-Factorization Conjecture if the vertex
degree is at least $0.823|V(G)|$. Perković and Reed [18] showed in 1997 that
the 1-Factorization Conjecture is true for large regular graphs with vertex
degree at least $|V(G)|/(2-\varepsilon)$ for any $0<\varepsilon<1$. In 2016,
Csaba, Kühn, Lo, Osthus and Treglown [6] verified the conjecture for
sufficiently large $|V(G)|$. Much less is known about the truth of the
Overfull Conjecture if we no longer require that $G$ is regular. It was
confirmed for graphs with $\Delta(G)\geq|V(G)|-3$ by Chetwynd and Hilton in
1989 [4]. Plantholt [19] in 2004 verified the conjecture for graphs of even
order and minimum degree at least $0.8819|V(G)|$. More recently, Plantholt
[20] showed the conjecture for sufficiently large even order graphs with
minimum degree at least $\frac{2}{3}|V(G)|$. Plantholt [23] and the author
extended these results and gave an asymptotic result for general graphs that
is similar to the Perković-Reed result for regular graphs, by showing the
following result: 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. All the results
mentioned above on graphs with minimum degree constraints are for graphs of
even order. In this paper, we obtain the first result (as far as we know) on
the Overfull Conjecture with large minimum degree constraints for graphs of
odd order.

######  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-1\geq n_{0}$ vertices with
$\delta(G)\geq(1+\varepsilon)n$, then $\chi^{\prime}(G)=\Delta(G)$ if and only
if $G$ is not overfull. 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.3 by applying Theorem 3.1 from Section 3. Theorem 3.1 is then proved
in the last section.

##  2 Notation and preliminaries

###  2.1 Results on degree sequences, paths, matchings, and overfull graphs

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

######  Theorem 2.1.

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.2 ([7]).

If $G$ is a graph on $n\geq 3$ vertices with $\delta(G)\geq\frac{n}{2}$, then
$G$ is hamiltonian.

Following the proof of Dirac [7], a hamiltonian cycle can be constructed in
polynomial time in $n$ if $\delta(G)\geq\frac{n}{2}$. In fact, there is a
polynomial time algorithm that constructs the closure of a graph $G$ and finds
a hamiltonian cycle of $G$ if its closure is a complete graph (see [1,
Exercise 4.2.15, page 62]).

A path $P$ connecting two vertices $u$ and $v$ is called a $(u,v)$-path, and
we write $uPv$ or $vPu$ in order to specify 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$.

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)$.

######  Lemma 2.3 ([23]).

Let $0<\frac{1}{n_{0}}\ll\varepsilon<1$, and $G$ be graph on $n\geq n_{0}$
vertices such that $\delta(G)\geq\frac{1}{2}(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 $\frac{\varepsilon n}{8}$. Then there exist vertex-
disjoint paths $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.

A multigraph $G$ is a _star-multigraph_ if $G$ has a vertex $x$ that is
incident with all multiple edges of $G$. In other words, $G-x$ is a simple
graph. The vertex $x$ is called the _multi-center_ of $G$.

######  Lemma 2.4.

Let $0<\frac{1}{n_{0}}\ll\eta\ll\varepsilon<1$, and $G$ be start-multigraph
graph on $n\geq n_{0}$ vertices such that
$\delta(G)\geq\frac{1}{2}(1+\varepsilon)n$ and $\mu(x)<\eta n$, where $x$ is
the multi-center of $G$. 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
$\frac{\varepsilon n}{13}$. If
$|N_{G}(x)\setminus\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}|\geq 2$, then there
exist vertex-disjoint paths $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. By relabeling the matching edges if necessary, assume that if
$x\in\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$, then $x=a_{t}$.

If $x\in\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$ and so $x=a_{t}$, then let
$a_{t}^{\prime}\in N_{G}(x)\setminus\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$, and
$M^{\prime}=(M\setminus\\{a_{t}b_{t}\\})\cup\\{a_{t}^{\prime}b_{t}\\}$. If
$x\not\in\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$, then let $x_{1},x_{2}\in
N_{G}(x)\setminus\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$ be distinct, and let
$M^{\prime}=(M\setminus\\{a_{t}b_{t}\\})\cup\\{a_{t}x_{1},x_{2}b_{t}\\}$.

Note that $\delta(G-x)\geq\frac{1}{2}(1+\varepsilon)n-\eta
n\geq\frac{1}{2}(1+\frac{2\varepsilon}{3})n$ and
$|M^{\prime}|\leq\frac{\varepsilon n}{13}+1<\frac{\varepsilon n}{12}$.
Applying Lemma 2.3 to $G-x$ with matching $M^{\prime}$, we find vertex-
disjoint paths $P^{\prime}_{1},\ldots,P^{\prime}_{t}$ in $G-x$ such that
$\bigcup V(P^{\prime}_{i})=V(G-x)$. Furthermore, if $x=a_{t}$,
$P^{\prime}_{i}$ joins $a_{i}$ to $b_{i}$ for $i\in[1,t-1]$, and
$P_{t}^{\prime}$ joins $a_{t}^{\prime}$ to $b_{t}$; if
$x\not\in\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$, $P^{\prime}_{i}$ joins $a_{i}$
to $b_{i}$ for $i\in[1,t-1]$, $P^{\prime}_{t}$ joins $a_{t}$ to $x_{1}$, and
$P_{t+1}^{\prime}$ joins $x_{2}$ to $b_{t}$. Letting $P_{i}=P_{i}^{\prime}$
for $i\in[1,t-1]$, and $P_{t}=a_{t}a_{t}^{\prime}P_{t}^{\prime}b_{t}$ if
$x=a_{t}$ and $P_{t}=a_{t}P_{t}^{\prime}x_{1}xx_{2}P^{\prime}_{t+1}b_{t}$ if
$x\not\in\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\}$ gives the desired paths for $G$
and $M$. By Lemma 2.3 and the simple adjustment on $M$ above, it is clear that
these paths can be found also in polynomial time. ∎

######  Lemma 2.5.

Let $G$ be a graph of order $2n$ and minimum degree at least 1. Assume that
except at most one vertex all other vertices have degree at least $n+1$ in
$G$. Then $G$ has a perfect matching, and the matching can be found in
polynomial time.

Proof. Let $u\in V(G)$ such that $d_{G}(u)=\delta(G)$. Since $\delta(G)\geq
1$, we let $v$ be a neighbor of $u$, and let $G_{1}=G-\\{u,v\\}$. Since
$\delta(G-u)\geq n$, we have $\delta(G_{1})\geq n-1=\frac{1}{2}(2n-2)$.
Applying Theorem 2.2, $G_{1}$ has a perfect matching $M$. Thus $M\cup\\{uv\\}$
is a perfect matching of $G$. By the construction of $G_{1}$ and the comments
immediately below Theorem 2.2, such a perfect matching of $G$ can be found in
polynomial time. ∎

######  Lemma 2.6.

Let $G[X,Y]$ be bipartite star-multigraph with $|X|=|Y|=n$ and multi-center
$x$. Suppose that $\delta(G)\geq 1$ and $\delta(G-x)\geq t$ for some
$t\in[1,n-1]$, and except at most $t$ vertices all other vertices of $G$ have
simple degree at least $\frac{n}{2}+1$ in $G$. Then $G$ has a perfect
matching. Furthermore, such a matching can be found in polynomial time.

Proof. Suppose, without loss of generality, that $x\in X$. As $\delta(G)\geq
1$, we let $y\in Y$ be a neighbor of $x$. Let $X^{\prime}=X\setminus\\{x\\}$
and $Y^{\prime}=Y\setminus\\{y\\}$. It suffices to show that
$G^{\prime}:=G[X^{\prime},Y^{\prime}]$ satisfies Hall’s Condition. If not, we
let $S\subseteq X^{\prime}$ with smallest cardinality such that
$|S|>|N_{G^{\prime}}(S)|$. Since $\delta(G^{\prime})\geq 1$, it follows that
$|S|\geq 1$. Then by the choice of $S$, we have $|S|=|N_{G^{\prime}}(S)|+1$
and $|N_{G^{\prime}}(S)|<|Y^{\prime}|$. As $|S|>|N_{G^{\prime}}(S)|$, it
follows that $|S|\geq\delta(G^{\prime})+1\geq t+1$. As $G^{\prime}$ has at
most $t$ vertices of degree less than $\frac{n}{2}$, $S$ contains a vertex of
degree at least $\frac{n}{2}$ in $G^{\prime}$ and so
$|N_{G^{\prime}}(S)|\geq\frac{n}{2}$. Thus $|S|>\frac{n}{2}$ and consequently
$|X^{\prime}\setminus S|<\frac{n}{2}$. Since
$|N_{G^{\prime}}(S)|<|Y^{\prime}|$, there exists $z\in Y^{\prime}\setminus
N_{G^{\prime}}(S)$ such that $N_{G^{\prime}}(z)\subseteq X^{\prime}\setminus
S$. As $\delta(G^{\prime})\geq t$, we have $|X^{\prime}\setminus S|\geq t$. As
$|Y^{\prime}\setminus
N_{G^{\prime}}(S)|=|Y^{\prime}|-|S|+1=|X^{\prime}|-|S|+1\geq t+1$ and
$G^{\prime}$ has at most $t$ vertices of degree less than $\frac{n}{2}$,
$Y^{\prime}\setminus N_{G^{\prime}}(S)$ contains a vertex of degree at least
$\frac{n}{2}$ in $G^{\prime}$. As a result, $|X^{\prime}\setminus
S|\geq\frac{n}{2}$, contradicting the earlier assertion that
$|X^{\prime}\setminus S|<\frac{n}{2}$. Hence $G^{\prime}$ has a perfect
matching.

There are polynomial time algorithms such as the Hopcroft-Karp algorithm [13]
in finding a maximum matching in any bipartite graph, thus a perfect matching
of $G$ can be found in polynomial time. ∎

######  Lemma 2.7.

Let $0<\frac{1}{n_{0}}\ll\varepsilon<1$ and $G$ be a star-multigraph with
multi-center $x$ on $2n\geq n_{0}$ vertices. Suppose that
$d_{G}(x)=\delta(G)$, $\delta(G-x)\geq(1+\varepsilon)n$, and $G-x$ contains no
$\Delta(G)$-overfull subgraph. Then $G$ contains no $\Delta(G)$-overfull
subgraph.

Proof. Let $X\subseteq V(G)$ with $|X|$ odd. We show that $G[X]$ is not
$\Delta(G)$-overfull. Assume first that $3\leq|X|\leq 2n-3$. By symmetry
between $X$ and $V(G)\setminus X$, we further assume $|X|\leq n$. Then as
$\delta(G-x)\geq(1+\varepsilon)n$ and $G-x$ is simple, we have

$e_{G}(X,V(G)\setminus
X)\geq(|X|-1)\big{(}(1+\varepsilon)n-|X|+1\big{)}>2n>\Delta(G).$

Thus $2e(G[X])<\Delta(G)|X|-\Delta(G)$ and so $G[X]$ is not
$\Delta(G)$-overfull. Thus, the only possible $\Delta(G)$-overfull subgraph of
$G$ is obtained from $G$ by deleting a single vertex. Note that if $G-u$ is
$\Delta(G)$-overfull for some $u\in V(G)$, then so is $G-x$ as $x$ has minimum
degree in $G$. However, $G-x$ is not $\Delta(G)$-overfull by our assumption.
Thus $G-u$ is not $\Delta(G)$-overfull for any $u\in V(G)$. Now as $G[X]$ is
not $\Delta(G)$-overfull for any $X\subseteq V(G)$ with $|X|$ odd, it follows
that $G$ contains no $\Delta(G)$-overfull subgraph. ∎

###  2.2 Results on edge colorings

Let $\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\in E(G)$ is incident to $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)\\}$. We simply write $\overline{\varphi}^{-1}(i)$
for $\overline{\varphi}^{-1}_{V(G)}(i)$.

For two distinct colors $\alpha,\beta\in[1,k]$, the components of the subgraph
induced by edges with colors $\alpha$ or $\beta$ are called
$(\alpha,\beta)$-chains. Each $(\alpha,\beta)$-chain is either a path or an
even cycle. 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 called a _Kempe change_.
For an $(\alpha,\beta)$-chain $P$, if it is a path with an endvertex $u$, we
also denote it by $P_{u}(\alpha,\beta,\varphi)$ to emphasis the endvertex $u$.
Let $u,v\in V(G)$. If $u$ and $u$ are contained in the same
$(\alpha,\beta)$-chain of $G$ with respect to $\varphi$, we say that $u$ and
$v$ are _$(\alpha,\beta)$ -linked_ with respect to $\varphi$.

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

######  Theorem 2.8 ([10, 25]).

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

######  Theorem 2.9 ([15]).

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

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. McDiarmid [16] observed the following result.

######  Theorem 2.10.

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
in $O(k^{2}|V(G)|^{2})$ time.

######  Lemma 2.11 ([23]).

Let $G$ be a star-multigraph on $2n$ vertices with multi-center $x$, and let
$A$ and $B$ be a partition of $V(G)$ with $|A|=|B|$, where we assume $x\in A$.
If $e(A)=e(B)$, $E_{G}(A,B)=E_{G}(x,B)$, and $G$ has an edge coloring using
$k$ colors, then there exists an edge coloring $\varphi$ using $k$ colors such
that for each $i,j\in[1,k]$,
$|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$ and
$\left||\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|\right|\leq
2$. Furthermore, such a coloring $\varphi$ can be found in
$O(k^{2}n^{2})$-time.

######  Lemma 2.12.

Let $G$ be a star-multigraph on $2n$ vertices with multi-center $x$, and let
$A$ and $B$ be a partition of $V(G)$ with $|A|=|B|$, where we assume $x\in A$.
If $E_{G}(A,B)=E_{G}(x,B)$, then any edge $k$-coloring of $G$ can be modified
into an edge $k$-coloring $\varphi$ of $G$ such that the restrictions of
$\varphi$ on both $G[A]$ and $G[B]$ are equitable. Furthermore, such a
coloring $\varphi$ can be found in $O(k^{2}n^{2})$-time.

Proof. We choose an edge $k$-coloring $\varphi$ of $G$ such that

$g_{\varphi}:=\max_{C\in\\{A,B\\}}\max_{i,j}\left||\overline{\varphi}_{C}^{-1}(i)|-|\overline{\varphi}_{C}^{-1}(j)|\right|$

is smallest and subject to this, the number $h_{\varphi}$ of color pairs
$(i,j)$ with
$\left||\overline{\varphi}_{C}^{-1}(i)|-|\overline{\varphi}_{C}^{-1}(j)|\right|=g_{\varphi}$
is smallest. If $g_{\varphi}\leq 2$, then we are done. Thus $g_{\varphi}\geq
3$. We assume, without loss of generality, that there exist $i,j\in[1,k]$ such
that
$|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|=g_{\varphi}\geq
3$. As $E_{G}(A,B)=E_{G}(x,B)$ and different $(i,j)$-chains are vertex-
disjoint, at most one vertex from $\overline{\varphi}_{A}^{-1}(i)$ is
$(i,j)$-lined with a vertex from $B$. As
$|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|\geq 3$,
there exist distinct $u,v\in\overline{\varphi}_{A}^{-1}(i)$ such that
$P_{u}(i,j,\varphi)=P_{v}(i,j,\varphi)$. We now let
$\psi=\varphi/P_{u}(i,j,\varphi)$. Then $g_{\psi}\leq g_{\varphi}$ and
$h_{\psi}<h_{\varphi}$, showing a contradiction to the choice of $\varphi$.
Thus we can find a coloring $\varphi$ such that
$\left||\overline{\varphi}_{C}^{-1}(i)|-|\overline{\varphi}_{C}^{-1}(j)|\right|\leq
2$ for any $C\in\\{A,B\\}$ and all $i,j\in[1,k]$.

There are at most ${k\choose 2}$ color pairs, each color pair takes
$O(n)$-time to reduce the difference of the two corresponding color classes by
2, and $O(n)$ steps to make the two corresponding color classes close in size.
Thus a desired edge coloring $\varphi$ can be found in $O(k^{2}n^{2})$-time. ∎

######  Lemma 2.13 ([23]).

If $G$ is a star-multigraph, then $\chi^{\prime}(G)\leq\Delta(G)+1$.
Furthermore, an edge coloring of $G$ using at most $\Delta(G)+1$ colors can be
found in polynomial time.

A multigraph $G$ is a _near star-multigraph_ with multi-center $x$ if, in
$G-x$, there is at most one pair of vertices $u$ and $v$ such that
$e_{G-x}(u,v)\geq 2$.

######  Lemma 2.14.

Let $G$ be a near star-multigraph with multi-center $x$ such that
$\mu(G-x)=e_{G-x}(y,z)$ for some $y,z\in V(G-x)$. Then
$\chi^{\prime}(G)\leq\max\\{\Delta(G)+e_{G}(y,z),\Delta(G)+1\\}$. Furthermore,
an edge $\max\\{\Delta(G)+e_{G}(y,z),\Delta(G)+1\\}$-coloring of $G$ can be
found in polynomial time.

Proof. We may assume $e_{G}(y,z)\geq 2$, as otherwise the statement follows
from Lemma 2.13. Let $G^{\prime}$ be obtained from $G$ by deleting
$e_{G}(y,z)-1$ edges joining $y$ and $z$. Applying Lemma 2.13 on $G^{\prime}$,
we have $\chi^{\prime}(G^{\prime})\leq\Delta(G^{\prime})+1\leq\Delta(G)+1$.
Now based on any edge $(\Delta(G^{\prime})+1)$-coloring of $G^{\prime}$,
coloring each of the deleted edges using a distinct color gives an edge
$(\Delta(G^{\prime})+1+e_{G}(y,z)-1)$-coloring of $G$. As
$\Delta(G^{\prime})+1+e_{G}(y,z)-1\leq\Delta(G)+e_{G}(y,z)$, we have
$\chi^{\prime}(G)\leq\Delta(G)+e_{G}(y,z)$. By Lemma 2.13, there is a
polynomial time algorithm to edge color $G^{\prime}$ using at most
$\Delta(G)+1$ colors. Thus there is a polynomial time algorithm to edge color
$G$ using at most $\max\\{\Delta(G)+e_{G}(y,z),\Delta(G)+1\\}$ colors. ∎

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, see [9, Lemma 2.1].

######  Lemma 2.15 (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,k]$.

##  3 Proof of Theorem 1.3

For $u\in V(G)$, the _deficiency_ of $u$ in $G$ is
$\operatorname{def}_{G}(u):=\Delta(G)-d_{G}(u)$. For $U\subseteq V(G)$,
$\operatorname{def}_{G}(U)=\sum_{u\in U}\operatorname{def}_{G}(u)$. We simply
write $\operatorname{def}_{G}(V(G))$ as $\operatorname{def}(G)$. For an
integer $i\geq 1$, 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. The proof of Theorem 1.3 is based on
the following result, which will be proved in the last section.

######  Theorem 3.1.

For all $0<\varepsilon<1$, there exists $n_{0}$ and $\eta$ with
$0<\frac{1}{n_{0}}\ll\eta\ll\varepsilon$ such that the following statement
holds. Let $G$ be a near star-multigraph on $2n\geq n_{0}$ vertices with
multi-center $x$, and let $U=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq\eta
n\\}$. Suppose that $G$ satisfies one of the following five conditions:

  1. (a)

$G$ is a star-multigraph and is regular with
$\delta(G)\geq\delta(G-x)\geq(1+\frac{\varepsilon}{2})n$ and $\mu(x)<\eta n$.

  2. (b)

$G$ is regular with $\delta(G)\geq(1+\varepsilon)n$, and there exist distinct
$y,z\in V(G)\setminus\\{x\\}$ with the following properties:

    1. (i)

$d_{G}^{s}(x)\geq 2$ and there are at most $n^{\frac{1}{2}}$ neighbors $w$ of
$x$ satisfying $e_{G}(x,w)\geq\eta n$;

    2. (ii)

$y$ and $z$ are the only two possible vertices in $G-x$ with $e_{G-x}(y,z)\geq
2$ but $\mu(G-x)<n^{\frac{1}{2}}$; and

    3. (iii)

$d^{s}_{G}(w)\geq(1+\varepsilon)n$ for all $w\in V(G)\setminus\\{x\\}$.

  3. (c)

$G$ is a star-multigraph and is regular with $\delta(G)\geq(1+\varepsilon)n$,
and there exists $y\in V(G)\setminus\\{x\\}$ such that

    1. (i)

$2\leq d^{s}(x)<n^{\frac{1}{2}}$;

    2. (ii)

$d^{s}_{G}(y)\geq 2\varepsilon n$; and

    3. (iii)

$d^{s}_{G}(w)\geq(1+\varepsilon)n$ for all $w\in V(G)\setminus\\{x,y\\}$.

  4. (d)

$G$ is a star-multigraph and $G$ has two distinct vertices $y,z$ such that

    1. (i)

$\mu(x)<\eta n$;

    2. (ii)

$d_{G}(y)=d_{G}(z)=\delta(G)\geq(\frac{1}{2}+\frac{3\varepsilon}{2})n$ and
$\min\\{d^{s}_{G}(y),d_{G}^{s}(z)\\}>\Delta(G)-\frac{1}{2}(1-0.9\varepsilon)n$;
and

    3. (iii)

$d_{G}(w)=\Delta(G)\geq(1+\varepsilon)n$ and
$d_{G}^{s}(w)\geq(1+\varepsilon)n-\mu(x)\geq(1+0.9\varepsilon)n$ for all $w\in
V(G)\setminus\\{y,z\\}$.

  5. (e)

$G$ is a star-multigraph, $|U|\geq\eta n$,
$\delta(G)\geq\delta(G-x)\geq(1+\varepsilon)n$, and
$\mu(x)\leq\frac{2}{\eta}$.

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

######  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-1\geq n_{0}$ vertices with
$\delta(G)\geq(1+\varepsilon)n$, then $\chi^{\prime}(G)=\Delta(G)$ if and only
if $G$ is not overfull. Furthermore, there is a polynomial time algorithm that
finds an optimal coloring.

Proof. The general strategy for proving the first part of the statement is to
add a vertex to $G$ to produce a star-multigraph $G^{\prime}$ and then take
off some matchings or linear forests from $G^{\prime}$ such that the resulting
multigraph satisfies one of the conditions listed in Theorem 3.1. Choose
integer $n_{0}$ and a real number $\eta$ so that
$0<\frac{1}{n_{0}}\ll\eta\ll\varepsilon<1$.

If $\chi^{\prime}(G)=\Delta(G)$, then clearly $G$ contains no
$\Delta(G)$-overfull subgraph. Thus we assume that $G$ is not overfull and
show $\chi^{\prime}(G)=\Delta(G)$. Since $n$ is odd and $G$ is not overfull,
we have $\operatorname{def}(G)\geq\Delta(G)$. We call a vertex of degree less
than $\Delta(G)$ but greater than $\delta(G)$ a _middle degree_ vertex. Let

$W=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq\eta n\\}.$

We consider the following four cases regarding the size of $W$.

Case 1. $|W|\geq 2\eta n$.

We let $W^{\prime}\subseteq W$ be a set of $\lfloor\eta n\rfloor$ vertices,
and let $x$ be a new vertex. We form a new graph $G^{\prime}$ as follows: add
at most $\lfloor\frac{2}{\eta}\rfloor$ edges between $x$ and each vertex of
$W^{\prime}$ one by one until the degree of $x$ in the resulting multigraph
reaches to $\delta(G)$. Since $\lfloor\frac{2}{\eta}\rfloor\times\lfloor\eta
n\rfloor=2n>\delta(G)$ (we can choose $\eta$ so that $\frac{1}{\eta}$ is an
integer), the star-multigraph $G^{\prime}$ exists. As $\eta
n>\lfloor\frac{2}{\eta}\rfloor$, we have $\Delta(G^{\prime})=\Delta(G)$. By
Lemma 2.7, $G^{\prime}$ contains no $\Delta(G^{\prime})$-overfull subgraph.

For each vertex $u\in V(G^{\prime})\setminus\\{x\\}$, we have
$d^{s}_{G}(u)\geq\delta(G)\geq(1+\varepsilon)n$. For each vertex $w\in
W\setminus W^{\prime}$, we have
$\Delta(G^{\prime})-d_{G^{\prime}}(w)=\Delta(G)-d_{G}(w)\geq\eta n$.
Furthermore, $|W\setminus W^{\prime}|\geq\eta n$. Now with $W\setminus
W^{\prime}$ playing the role of $U$ in Theorem 3.1(e) and applying Theorem
3.1, we see that $\chi^{\prime}(G^{\prime})=\Delta(G^{\prime})=\Delta(G)$ and
so $\chi^{\prime}(G)=\Delta(G)$.

Case 2. $|W|=0$.

The proof of this case is similar to the beginning part in the proof of
Theorem 1.3 in [23], but we repeat it to be self-contained. Note that $|W|=0$
implies that $\Delta(G)-\delta(G)<\eta n$. Let $x$ be a new vertex and let
$G^{\prime}$ be obtained from $G$ by adding $x$ to $G$ and adding some edges
between $x$ and vertices $y\in V(G)$ with $d_{G}(y)<\Delta(G)$ with the
following constraints:

  1. (1)

$d_{G^{\prime}}(x)=\delta(G^{\prime})=\delta(G)$ and
$\Delta(G^{\prime})=\Delta(G)$;

  2. (2)

subject to (1), at most one neighbor of $x$ in $G^{\prime}$ is not a maximum
degree vertex of $G^{\prime}$.

Let $V(G)=\\{x_{1},\ldots,x_{2n-1}\\}$ and assume $d_{G}(x_{1})\leq\ldots\leq
d_{G}(x_{2n-1})$. Note $d_{G}(x_{2n-1})=\Delta(G)$. Let $s\in[1,2n-2]$ be the
smallest integer such that
$\sum_{i=1}^{s}\operatorname{def}_{G}(x_{i})\geq\delta(G)$; such an integer
$s$ exists since $\operatorname{def}(G)\geq\Delta(G)$. For each $i\in[1,s-1]$,
we add exactly $\operatorname{def}_{G}(x_{i})$ edges between $x$ and $x_{i}$,
and we add $\delta(G)-\sum_{i=1}^{s-1}\operatorname{def}_{G}(x_{i})$ edges
between $x$ and $x_{s}$, and call $G^{\prime}$ the resulting multigraph. It is
clear that $G^{\prime}$ satisfies constraints (1) and (2). Since
$\Delta(G)-\delta(G)<\eta n$, we have

$|N_{G^{\prime}}(x)|\geq\frac{(1+\varepsilon)n}{\eta n}>3.$

By Lemma 2.7, $G^{\prime}$ contains no $\Delta(G^{\prime})$-overfull subgraph.

Since $x$ has the smallest degree in $G^{\prime}$ and $G=G^{\prime}-x$ is not
overfull, we get $\sum_{i\geq
1}\operatorname{def}_{G^{\prime}}(x_{i})\geq\operatorname{def}_{G^{\prime}}(x)$.
Since $|V(G^{\prime})|=2n$ is even,
$\operatorname{def}_{G^{\prime}}(x)+\sum_{i\geq
1}\operatorname{def}_{G^{\prime}}(x_{i})$ is even. Then by Theorem 2.1, there
exists a multigraph $H$ on $V(G^{\prime})$ such that
$d_{H}(x)=\operatorname{def}_{G^{\prime}}(x)$ and
$d_{H}(x_{i})=\operatorname{def}_{G^{\prime}}(x_{i})$ for each $i\in[1,2n-1]$.
The multigraph $H$ will aid us in finding a spanning regular subgraph of
$G^{\prime}$.

Note that
$\Delta(H)=\operatorname{def}_{G^{\prime}}(x)=\Delta(G)-\delta(G)<\eta n$ and
$H$ contains isolated vertices. Thus $\chi^{\prime}(H)\leq\Delta(H)+\mu(H)\leq
2\Delta(H)<2\eta n$ by Theorem 2.8. Hence we can greedily partition $E(H)$
into $k\leq 52\frac{\eta n}{\varepsilon}$ matchings $M_{1},\ldots,M_{k}$ each
of size at most $\frac{\varepsilon n}{26}$. Now we take out linear forests
(union of vertex-disjoint paths) from $G^{\prime}$ by applying Lemma 2.4 with
$M_{1},\ldots,M_{k}$. As at most one neighbor of $x$ is not a maximum degree
vertex of $G^{\prime}$, it follows that $x$ is adjacent in $G^{\prime}$ to at
most one vertex of those vertices covered by $M_{i}$ for each $i\in[1,k]$.
More precisely, define spanning subgraphs $G_{0},\ldots,G_{k}$ of $G^{\prime}$
and edge-disjoint linear forests $F_{1},\ldots,F_{k}$ such that

  1. (1)

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

  2. (2)

$F_{i}$ is a spanning linear forest in $G_{i-1}$ whose leaves are precisely
the vertices in $M_{i}$.

Let $G_{0}=G^{\prime}$ 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 104\frac{\eta
n}{\varepsilon}$, it follows that
$\delta(G_{i-1})\geq(1+\varepsilon)n-104\frac{\eta
n}{\varepsilon}\geq(1+\frac{\varepsilon}{2})n$. Furthermore, by the
construction of $F_{1},\ldots,F_{i-1}$, we know that maximum degree vertices
of $G^{\prime}$ are still maximum degree vertices of $G_{i-1}$. Thus in
$G_{i-1}$, still at most one neighbor of $x$ is not a maximum degree vertex of
$G_{i-1}$. As $\mu(x)<\eta n$ and
$\delta(G_{i-1})\geq(1+\frac{\varepsilon}{2})n$, $x$ has at least two
neighbors in $G_{i-1}$ that are not covered by $M_{i}$. Since $M_{i}$ has size
at most $\frac{\varepsilon n}{26}$, we can apply Lemma 2.4 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^{\prime}}(u)$.
Thus

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

Note that $\mu(x)<\eta n$ and
$\delta(G_{k}-x)\geq(1+\varepsilon)n-104\frac{\eta
n}{\varepsilon}-\mu(x)>(1+\frac{\varepsilon}{2})n$. Thus the multigraph
$G_{k}$ satisfies Condition (a) of Theorem 3.1. Now
$\chi^{\prime}(G_{k})=\Delta(G_{k})$ by Theorem 3.1. We color the edges of
$F_{i}$ using 2 distinct colors from
$[\Delta(G^{\prime})-2k+1,\Delta(G^{\prime})]$ 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^{\prime}$
using $\Delta(G_{k})+2k=\Delta(G^{\prime})$ colors. Since $G$ is a subgraph of
$G^{\prime}$ and $\Delta(G)=\Delta(G^{\prime})$, it follows that
$\chi^{\prime}(G)=\Delta(G)$.

Case 3. $n^{\frac{1}{2}}\leq|W|<2\eta n$.

We add a new vertex $x$. For each vertex $v\in V(G)\setminus(V_{\Delta}\cup
W)$, we add $\operatorname{def}_{G}(v)$ edges between $x$ and $v$ until the
degree of $x$ reaches to $\delta(G)$. If the degree of $x$ reaches to
$\delta(G)$ already in this process, we denote the resulting multigraph by
$G^{\prime}$. If the degree of $x$ is still less than $\delta(G)$ after we
adding edges between $x$ and all vertices of $V(G)\setminus(V_{\Delta}\cup
W)$, then we add at most $2n^{\frac{1}{2}}$ edges between $x$ and each vertex
of $W$ until the degree of $x$ reaches to $\delta(G)$. Denote the resulting
multigraph by $G^{\prime}$. As
$\operatorname{def}(G)\geq\operatorname{def}_{G}(W)>\Delta$ and
$d_{G^{\prime}}(x)=\delta(G)$, it follows that $G^{\prime}$ is not regular.

Note that $V_{\delta}(G^{\prime})\subseteq W\cup\\{x\\}$ by the construction
of $G^{\prime}$ and so $|V_{\delta}(G^{\prime})|\leq 2\eta n+1$. Thus for any
$v\in V(G^{\prime})\setminus V_{\delta}(G^{\prime})$,
$\delta(G^{\prime}-v-V_{\delta}(G^{\prime}))\geq n$ and so both
$G^{\prime}-V_{\delta}(G^{\prime})$ and $G^{\prime}-v-V_{\delta}(G^{\prime})$
are hamiltonian by Theorem 2.2. Thus if $G^{\prime}-V_{\delta}(G^{\prime})$
and $G^{\prime}-v-V_{\delta}(G^{\prime})$ have even order, then they each has
a perfect matching. Hence if $|V_{\delta}(G^{\prime})|$ is even, we can
decrease $\Delta(G^{\prime})-\delta(G^{\prime})$ but preserve
$\delta(G^{\prime})$ in deleting a prefect matching $M$ of
$G^{\prime}-V_{\delta}(G^{\prime})$. If $|V_{\delta}(G^{\prime})|$ is odd but
$G^{\prime}$ has a middle degree vertex $v$, we can decrease
$\Delta(G^{\prime})-\delta(G^{\prime})$ but preserve $\delta(G^{\prime})$ in
deleting a prefect matching $M$ of $G^{\prime}-v-V_{\delta}(G^{\prime})$.
Denote by $G_{1}$ the reduced multigraph from $G^{\prime}$ by deleting $M$ in
either of these two cases. We show in the following that we can consider
$G_{1}$ in the place of $G^{\prime}$. As
$\delta(G_{1}-x)=\delta(G^{\prime}-x)\geq(1+\varepsilon)n$, $G_{1}[X]$ is not
$\Delta(G_{1})$-overfull for any $X\subseteq V(G_{1})$ with $3\leq|X|\leq
2n-3$. Thus to show that $G_{1}$ contains no $\Delta(G_{1})$-overfull
subgraph, we show that $G_{1}-u$ is not $\Delta(G_{1})$-overfull for any $u\in
V(G_{1})$. If $|V_{\delta}(G^{\prime})|\geq 2$, then for any $u\in V(G_{1})$
and $v\in V_{\delta}(G_{1})$, we have

$\displaystyle\sum_{w\in V(G_{1}-u)}\left(\Delta(G_{1})-d_{G_{1}-u}(w)\right)$
$\displaystyle=$ $\displaystyle
d_{G_{1}}(u)+(\Delta(G_{1})-d_{G_{1}}(v))+\operatorname{def}_{G_{1}}(V(G_{1})\setminus\\{u,v\\})$
$\displaystyle\geq$
$\displaystyle\Delta(G_{1})+\operatorname{def}_{G_{1}}(V(G_{1})\setminus\\{u,v\\})\geq\Delta(G_{1}).$

Thus $G_{1}-u$ is not $\Delta(G_{1})$-overfull. If
$|V_{\delta}(G^{\prime})|=1$, then $V_{\delta}(G^{\prime})=\\{x\\}$. Note that
$x\in V_{\delta}(G_{1})$ and the middle degree vertex, say $v$, exists in
$G^{\prime}$. Then

$\displaystyle\operatorname{def}(G_{1}-x)$ $\displaystyle=$ $\displaystyle
d_{G^{\prime}}(x)+(\Delta(G_{1})-d_{G^{\prime}}(v))+\operatorname{def}_{G_{1}}(V(G_{1})\setminus\\{x,v\\})$
$\displaystyle=$ $\displaystyle
d_{G^{\prime}}(x)+(\Delta(G^{\prime})-1-d_{G^{\prime}}(v))+\operatorname{def}_{G^{\prime}}(V(G^{\prime})\setminus\\{x,v\\})$
$\displaystyle=$ $\displaystyle\sum_{w\in
V(G^{\prime}-x)}(\Delta(G^{\prime})-d_{G^{\prime}-x}(w))-1.$

Since $G^{\prime}$ contains no $\Delta(G^{\prime})$-overfull subgraph, we have
$\sum_{w\in
V(G^{\prime}-x)}(\Delta(G^{\prime})-d_{G^{\prime}-x}(w))\geq\Delta(G^{\prime})$.
Thus $\operatorname{def}(G_{1}-x)\geq\Delta(G^{\prime})-1=\Delta(G_{1})$ and
so $G_{1}$ contains no $\Delta(G_{1})$-overfull subgraph. Furthermore,
$\chi^{\prime}(G_{1})=\Delta(G_{1})$ implies that
$\chi^{\prime}(G^{\prime})=\Delta(G^{\prime})$. Thus when
$|V_{\delta}(G^{\prime})|$ is even or $G^{\prime}$ has a middle degree vertex,
we can consider $G_{1}$ in the place of $G^{\prime}$ and show that $G_{1}$ is
a class 1 graph.

Thus we assume that $|V_{\delta}(G^{\prime})|$ is odd and $G^{\prime}$ has no
middle degree vertex. This in particular, implies that $\delta(G^{\prime})$
and $\Delta(G^{\prime})$ have the same parity. As $G^{\prime}$ has no
$\Delta(G^{\prime})$-overfull subgraph, $|V_{\delta}(G^{\prime})|\geq 3$. Let
$y,z\in V_{\delta}(G^{\prime})\setminus\\{x\\}$ be distinct. We find a perfect
matching $M_{11}$ in $G-(V_{\delta}(G^{\prime})\setminus\\{y\\})$ and a
perfect matching $M_{12}$ in $G-(V_{\delta}(G^{\prime})\setminus\\{z\\})$. The
matchings exist by Theorem 2.2. Let $G_{1}=G^{\prime}-M_{11}-M_{12}$. We
repeat this same process and find a perfect matching $M_{21}$ in
$G_{1}-(V_{\delta}(G^{\prime})\setminus\\{y\\})$ and a perfect matching
$M_{22}$ in $G_{1}-(V_{\delta}(G^{\prime})\setminus\\{z\\})$. For
$i\in[2,(\Delta(G^{\prime})-\delta(G^{\prime}))/2]$, we let
$G_{i}=G_{i-1}-M_{i1}-M_{i2}$. Since
$d_{G^{\prime}}(y)\geq\delta(G^{\prime})+e_{G^{\prime}}(x,y)\geq(1+\varepsilon)n+e_{G^{\prime}}(x,y)$
and
$d_{G^{\prime}}(z)\geq\delta(G^{\prime})+e_{G^{\prime}}(x,z)\geq(1+\varepsilon)n+e_{G^{\prime}}(x,z)$,
we have $d^{s}_{G_{i}}(y),d^{s}_{G_{i}}(z)\geq\delta(G^{\prime})-i$. As
$\Delta(G^{\prime})-\delta(G^{\prime})<2n-(1+\varepsilon)n=(1-\varepsilon)n$,
we see that
$d^{s}_{G_{i}}(y)=d^{s}_{G_{i}}(z)=\delta(G^{\prime})-i\geq(1+\varepsilon)n-\frac{1}{2}(1-\varepsilon)n\geq(\frac{1}{2}+\frac{3\varepsilon}{2})n$.
For any vertex $w\in V(G_{i})\setminus\\{x,y,z\\}$,
$d^{s}_{G_{i}}(w)\geq\delta(G)-\mu(x)\geq(1+0.9\varepsilon)n$. As
$|V_{\delta}(G^{\prime})|+1<2\eta n+1\ll 0.9\varepsilon n$, both
$G_{i}-(V_{\delta}(G^{\prime})\setminus\\{y\\})$ and
$G_{i}-(V_{\delta}(G^{\prime})\setminus\\{z\\})$ satisfy the condition of
Lemma 2.5, and so each has a perfect matching. Thus for each
$i\in[2,(\Delta(G^{\prime})-\delta(G^{\prime}))/2]$, we find matchings
$M_{i1}$ and $M_{i2}$ respectively from
$G_{i-1}-(V_{\delta}(G^{\prime})\setminus\\{y\\})$ and
$G_{i-1}-(V_{\delta}(G^{\prime})\setminus\\{z\\})$. We claim that
$G^{*}:=G_{(\Delta(G^{\prime})-\delta(G^{\prime}))/2}$ satisfies Condition (d)
of Theorem 3.1. We have

  1. (i)

$\mu(x)<\eta n$, as there might be edges in $G^{\prime}$ between $x$ and
vertices of $V(G)\setminus(V_{\Delta}\cup W)$;

  2. (ii)

$d_{G^{*}}(y)=d_{G^{*}}(z)=\delta(G^{*})\geq(\frac{1}{2}+\frac{3\varepsilon}{2})n$;

  3. (iii)

$\min\\{d_{G^{*}}^{s}(y),d_{G^{*}}^{s}(z)\\}\geq\Delta(G^{*})-(\Delta(G^{\prime})-\delta(G^{\prime}))/2-\mu(x)\geq\Delta(G^{*})-\frac{1}{2}(1-\varepsilon)n-\mu(x)>\Delta(G^{*})-\frac{1}{2}(1-0.9\varepsilon)n$;

  4. (iv)

$d_{G^{*}}(w)=\Delta(G^{*})\geq(1+\varepsilon)n$ and
$d_{G^{*}}^{s}(w)\geq(1+\varepsilon)n-\mu(x)\geq(1+0.9\varepsilon)n$ for all
$w\in V(G^{*})\setminus\\{y,z\\}$.

By Theorem 3.1, $\chi^{\prime}(G^{*})=\Delta(G^{*})=\delta(G^{\prime})$.
Taking an edge $\delta(G^{\prime})$-coloring of $G^{*}$, coloring edges in
$M_{i1}$ with color $\delta(G^{\prime})+2i-1$ and coloring edges in $M_{i2}$
with color $\delta(G^{\prime})+2i$ for each
$i\in[1,(\Delta(G^{\prime})-\delta(G^{\prime}))/2]$, we obtain an edge
$\Delta(G^{\prime})$-coloring of $G^{\prime}$ and so an edge
$\Delta(G)$-coloring of $G$.

Case 4. $0<|W|<n^{\frac{1}{2}}$.

We may assume that $|V_{\delta}|\geq 2$. Otherwise, suppose $|V_{\delta}|=1$;
we let $M$ be a perfect matching of $G-V_{\delta}$ and let $G_{1}=G-M$. As
$\operatorname{def}(G)\geq\Delta(G)$ by our assumption, we have
$\operatorname{def}(G_{1})=\operatorname{def}(G)-1\geq\Delta(G)-1=\Delta(G_{1})$.
We claim that $G_{1}$ contains no $\Delta(G_{1})$-overfull subgraph. As
$\delta(G_{1})\geq(1+\varepsilon)n$, $G_{1}[X]$ is not
$\Delta(G_{1})$-overfull for any $X\subseteq V(G_{1})$ with $3\leq|X|\leq
2n-3$. Thus the only possible $\Delta(G_{1})$-overfull subgraph in $G_{1}$ is
$G_{1}$ itself. However $\operatorname{def}(G_{1})\geq\Delta(G_{1})$ implies
that $G_{1}$ is not overfull. Since $\delta(G_{1})=\delta(G)$, and
$\chi^{\prime}(G_{1})=\Delta(G_{1})$ implies that
$\chi^{\prime}(G)=\Delta(G)$, we can consider $G_{1}$ in the place of $G$.

Next we may assume that $\operatorname{def}(G)\geq\Delta(G)+|W|+1$. For
otherwise, we let $y,z\in V_{\delta}$ be distinct and add
$(\operatorname{def}(G)-\Delta(G))/2$ edges between $y$ and $z$ to get $G^{*}$
(note that $\operatorname{def}(G)-\Delta(G)$ is even as
$\operatorname{def}(G)=(2n-1)\Delta(G)-2|E(G)|$), and now add a new vertex $x$
and $\Delta(G)$ edge between $x$ and the vertices of degree less $\Delta(G)$
in $G^{*}$ to get a $\Delta$-regular graph $G^{\prime}$. Note that
$G^{\prime}$ may not be star-multiple, but all the possible multiple edges in
$G^{\prime}-x$ are between $y$ and $z$ and
$e_{G^{\prime}}(y,z)\leq\frac{1}{2}|W|+1<n^{\frac{1}{2}}$. As
$\operatorname{def}_{G^{*}}(w)<\Delta(G^{*})$ for any $w\in V(G^{*})$, we know
that $d_{G^{\prime}}^{s}(x)\geq 2$. By Theorem 3.1(b), we have
$\chi^{\prime}(G^{\prime})=\Delta(G^{\prime})=\Delta(G)$ and so
$\chi^{\prime}(G)=\Delta(G)$.

Thus $\operatorname{def}(G)\geq\Delta(G)+|W|+1$. Note that
$V_{\delta}\subseteq W$ and so $|V_{\delta}|\leq|W|<n^{\frac{1}{2}}$. We may
further assume that $|V_{\delta}|$ is even and $G$ has no middle degree
vertex. For otherwise, if $|V_{\delta}|$ is odd, then $G-V_{\delta}$ has a
perfect matching $M$; if $|V_{\delta}|$ is even and $G$ has a middle degree
vertex $v$, then $G-v-V_{\delta}$ has a perfect matching $M$. In both cases,
let $G_{1}=G-M$. As $\operatorname{def}(G)\geq\Delta(G)+|W|+1$, we have
$\operatorname{def}(G_{1})\geq\Delta(G)-|W|-1\geq\Delta(G)>\Delta(G_{1})$.
Thus $G_{1}$ is not overfull. Furthermore, as
$\delta(G_{1})=\delta(G)\geq(1+\varepsilon)n$, $G_{1}[X]$ is not
$\Delta(G_{1})$-overfull for any $X\subseteq V(G_{1})$ with $3\leq|X|\leq
2n-3$. Thus $G_{1}$ contains no $\Delta(G_{1})$-overfull subgraph. Furthermore
$\chi^{\prime}(G_{1})=\Delta(G_{1})$ implies that
$\chi^{\prime}(G)=\Delta(G)$. Thus we can consider $G_{1}$ in the place of
$G$.

Thus we may assume that $|V_{\delta}|\geq 2$ is even,
$\operatorname{def}(G)\geq\Delta(G)+|W|+1$, and $G$ has no middle degree
vertex. Let $x$ be a new vertex and $y\in V_{\delta}$. We first add
$\operatorname{def}_{G}(y)$ edges between $x$ and $y$ and denote the resulting
graph by $G^{\prime}$. Note that $V_{\delta}(G^{\prime})=\\{x\\}$. Denote by
$\delta^{\prime}$ the second minimum degree of $G^{\prime}$. Then we add edges
between $x$ and vertices of
$V_{\delta^{\prime}}(G^{\prime})=V_{\delta}\setminus\\{y\\}$ as follows:

  1. Step 1

If $|V_{\delta^{\prime}}(G^{\prime})|+d_{G^{\prime}}(x)\leq\delta^{\prime}+1$,
then add an edge between $x$ and each vertex from
$V_{\delta^{\prime}}(G^{\prime})$ and update $G^{\prime}$ to be the resulting
multigraph; otherwise,
$|V_{\delta^{\prime}}(G^{\prime})|+d_{G^{\prime}}(x)\geq\delta^{\prime}+2$,
then we add an edge between $x$ and each vertex of a selected set of
$\delta^{\prime}-d_{G^{\prime}}(x)$ vertices from
$V_{\delta^{\prime}}(G^{\prime})$ and update $G^{\prime}$ to be the resulting
multigraph.

  2. Step 2

If $|V_{\delta}(G^{\prime})|\geq 2$, then stop; otherwise, return to Step 1.

Since $\operatorname{def}(G)>\Delta(G)$ and $|V_{\Delta}|\geq 1$, the process
above stops before or when the degree of $x$ reaches to $\Delta(G)$. Thus
$\Delta(G^{\prime})=\Delta(G)$. Furthermore, we have
$d_{G^{\prime}}(x)=\delta(G^{\prime})\geq\delta(G)$ and
$d^{s}_{G^{\prime}}(x)\geq 2$. Lastly by the process, we have that $x\in
V_{\delta}(G^{\prime})$, $|V_{\delta}(G^{\prime})|\geq 2$, and $0\leq
d_{G^{\prime}}(w)-d_{G^{\prime}}(x)\leq 1$ for any $w\in
N_{G^{\prime}}(x)\setminus\\{y\\}$. Actually, as
$\operatorname{def}_{G}(y)+|W|\leq(1-\varepsilon)n+n^{\frac{1}{2}}<\delta(G)$,
the construction of $G^{\prime}$ implies $N_{G^{\prime}}(x)=W$. As
$G=G^{\prime}-x$ is not overfull and $d_{G^{\prime}}(x)=\delta(G)$, we know
that $G^{\prime}-u$ is not overfull for any $u\in V(G^{\prime})$. Also, as
$\delta(G^{\prime}-x)\geq(1+\varepsilon)n$, by calculation, $G^{\prime}[X]$ is
not $\Delta(G^{\prime})$-overfull for any $X\subseteq V(G^{\prime})$ with
$3\leq|X|\leq 2n-3$. Thus $G^{\prime}$ contains no
$\Delta(G^{\prime})$-overfull subgraph. If $G^{\prime}$ is regular, then as
$2\leq d^{s}_{G^{\prime}}(x)\leq|W|$ and
$d_{G^{\prime}}^{s}(w)\geq(1+\varepsilon)n$ for any $w\in
V(G^{\prime})\setminus\\{x\\}$, we are done by Theorem 3.1(c).

Thus we assume that $G^{\prime}$ is not regular. Since $G$ has no middle
degree vertex, we have $|V(G^{\prime})\setminus
V_{\Delta}(G^{\prime})|\leq|(V_{\delta}(G)\setminus\\{y\\})\cup\\{x\\}|<n^{\frac{1}{2}}$.
Since $\delta^{s}(G^{\prime}-x)\geq(1+\varepsilon)n$, it follows that for any
$v\in V(G^{\prime})\setminus V_{\delta}(G^{\prime})$, in the graph
$G^{\prime}-v-V_{\delta}(G^{\prime})$, every vertex has degree at least $n+1$
except possibly for the vertex $y$, which has degree at least
$(1+\varepsilon)n-(2n-(1+\varepsilon)n)-|W|-1>1$. Thus both
$G^{\prime}-V_{\delta}(G^{\prime})$ and $G^{\prime}-v-V_{\delta}(G^{\prime})$
have a perfect matching by Lemma 2.5. Thus if
$G^{\prime}-V_{\delta}(G^{\prime})$ and $G^{\prime}-v-V_{\delta}(G^{\prime})$
have even order, then they each has a perfect matching. Hence if
$|V_{\delta}(G^{\prime})|$ is even, we can decrease
$\Delta(G^{\prime})-\delta(G^{\prime})$ but preserve $\delta(G^{\prime})$ in
deleting a prefect matching $M$ of $G^{\prime}-V_{\delta}(G^{\prime})$. If
$|V_{\delta}(G^{\prime})|$ is odd but $G^{\prime}$ has a middle degree vertex
$v$, we can decrease $\Delta(G^{\prime})-\delta(G^{\prime})$ but preserve
$\delta(G^{\prime})$ in deleting a prefect matching $M$ of
$G^{\prime}-v-V_{\delta}(G^{\prime})$. Denote by $G_{1}$ the reduced graph
from $G^{\prime}$ by deleting $M$ in either of these two cases. As
$\delta(G_{1})=\delta(G^{\prime})\geq(1+\varepsilon)n$, by the same argument
as in Case 3, we know that $G_{1}$ contains no $\Delta(G_{1})$-overfull
subgraph. Furthermore, $\chi^{\prime}(G_{1})=\Delta(G_{1})$ implies that
$\chi^{\prime}(G^{\prime})=\Delta(G^{\prime})$. Thus we can consider $G_{1}$
in the place of $G^{\prime}$ and show that $G_{1}$ is a class 1 graph.

Thus $G^{\prime}$ has no middle degree vertex. This in particular, implies
that $\delta(G^{\prime})$ and $\Delta(G^{\prime})$ have the same parity. Also,
as $0\leq d_{G^{\prime}}(w)-d_{G^{\prime}}(x)\leq 1$ for any $w\in
N_{G^{\prime}}(x)\setminus\\{y\\}$, it follows that
$d_{G^{\prime}}(w)=d_{G^{\prime}}(x)=\delta(G^{\prime})$ for any $w\in
N_{G^{\prime}}(x)\setminus\\{y\\}$. Since $W=V_{\delta}=N_{G^{\prime}}(x)$, we
know that $d_{G^{\prime}}(w)=d_{G^{\prime}}(x)=\delta(G^{\prime})$ for any
$w\in V_{\delta}\setminus\\{y\\}$. As $V(G)=V_{\Delta}\cup V_{\delta}$, and
$d_{G^{\prime}}(y)=\Delta(G^{\prime})$, it follows that
$V_{\delta}(G^{\prime})=(V_{\delta}\setminus\\{y\\})\cup\\{x\\}$ and so
$|V_{\delta}(G^{\prime})|$ is even and $|V_{\Delta}(G^{\prime})|$ is even. As
$\Delta(G^{\prime})-\delta(G^{\prime})\leq(1-\varepsilon)n$ and
$d^{s}_{G^{\prime}}(y)\geq(1+\varepsilon)n$, by Lemma 2.5,
$G^{\prime}-V_{\delta}(G^{\prime})$ has a perfect matching $M_{1}$. Let
$G_{1}=G^{\prime}-V_{\delta}(G^{\prime})-M_{1}$. By Lemma 2.5 again, we can
find a perfect matching $M_{2}$ in $G_{1}$. In general, we let
$G_{i}=G_{i-1}-M_{i}$ for each
$i\in[2,\Delta(G^{\prime})-\delta(G^{\prime})]$. We claim that $G_{i}$ has a
perfect matching $M_{i}$. Note that
$d_{G_{i}}(y)\geq(1+\varepsilon)n-(\Delta(G^{\prime})-\delta(G^{\prime}))-|V_{\delta}(G^{\prime})|\geq(1+\varepsilon)n-(1-\varepsilon)n-n^{\frac{1}{2}}\geq\varepsilon
n>1$ and
$d_{G_{i}}(z)\geq\delta(G^{\prime})-|V_{\delta}(G^{\prime})|\geq(1+\frac{\varepsilon}{2})n$.
Thus by Lemma 2.5, $G_{i}$ has a perfect matching $M_{i+1}$. The graph
$G^{*}:=G_{\Delta(G^{\prime})-\delta(G^{\prime})}$ is
$\delta(G^{\prime})$-regular satisfying the following conditions:

  1. (i)

$2\leq d^{s}_{G^{*}}(x)\leq|W|<n^{\frac{1}{2}}$;

  2. (ii)

$d^{s}_{G^{*}}(y)\geq(1+\varepsilon)n-(\Delta(G^{\prime})-\delta(G^{\prime}))\geq
2\varepsilon n$; and

  3. (iii)

$d^{s}_{G^{*}}(w)\geq(1+\varepsilon)n$ for all $w\in
V(G^{*})\setminus\\{x,y\\}$, because $w\not\in N_{G^{\prime}}(x)$ if $w\in
V(G^{*})\setminus(W\cup\\{x\\})$ and
$d_{G^{*}}^{s}(w)=d_{G^{\prime}}^{s}(w)\geq(1+\varepsilon)n$ for any $w\in
W\setminus\\{y\\}$.

Now by Theorem 3.1(c), $\chi^{\prime}(G^{*})=\Delta(G^{*})$. An edge
$\chi^{\prime}(G^{*})$-coloring of $G^{*}$ together with a coloring with the
edges in $M_{i}$ colored by $i$ for each
$i\in[\Delta(G^{*})+1,\Delta(G^{\prime})]$ gives an edge
$\Delta(G^{\prime})$-coloring of $G^{\prime}$ and so of $G$.

We lastly check that the procedure above yields a polynomial time algorithm.
If $G$ is overfull, then $\chi^{\prime}(G)=\Delta(G)+1$ and $G$ can be edge
colored using $\Delta(G)+1$ colors in polynomial time [17]. Thus $G$ is not
overfull. In each of the Cases 1 to 4, it is polynomial time (all the results
applied in the proof give appropriate running time statements) to reduce $G$
into a multigraph that satisfies one of the Conditions (a) to (e) as listed in
Theorem 3.1. Then we find an edge $\Delta(G)$-coloring of $G$ in polynomial
time by Theorem 3.1. ∎

##  4 Proof of Theorem 3.1

We will need the following result, which was proved using Chernoff bound.

######  Lemma 4.1 ([23], 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)$, where $1\leq t\leq n$
is an integer. 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^{\frac{2}{3}}-1$ for each $v\in V(G)$.

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

######  Theorem 1.4.

For all $0<\varepsilon<1$, there exists $n_{0}$ and $\eta$ with
$0<\frac{1}{n_{0}}\ll\eta\ll\varepsilon$ such that the following statement
holds. Let $G$ be a near star-multigraph on $2n\geq n_{0}$ vertices with
multi-center $x$, and let $U=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq\eta
n\\}$. Suppose that $G$ satisfies one of the following five conditions:

  1. (a)

$G$ is a star-multigraph and is regular with
$\delta(G)\geq\delta(G-x)\geq(1+\frac{\varepsilon}{2})n$ and $\mu(x)<\eta n$.

  2. (b)

$G$ is regular with $\delta(G)\geq(1+\varepsilon)n$, and there exist distinct
$y,z\in V(G)\setminus\\{x\\}$ with the following properties:

    1. (i)

$d_{G}^{s}(x)\geq 2$ and there are at most $n^{\frac{1}{2}}$ neighbors $w$ of
$x$ satisfying $e_{G}(x,w)\geq\eta n$;

    2. (ii)

$y$ and $z$ are the only two possible vertices in $G-x$ with $e_{G-x}(y,z)\geq
2$ but $\mu(G-x)<n^{\frac{1}{2}}$; and

    3. (iii)

$d^{s}_{G}(w)\geq(1+\varepsilon)n$ for all $w\in V(G)\setminus\\{x\\}$.

  3. (c)

$G$ is a star-multigraph and is regular with $\delta(G)\geq(1+\varepsilon)n$,
and there exists $y\in V(G)\setminus\\{x\\}$ such that

    1. (i)

$2\leq d^{s}(x)<n^{\frac{1}{2}}$;

    2. (ii)

$d^{s}_{G}(y)\geq 2\varepsilon n$; and

    3. (iii)

$d^{s}_{G}(w)\geq(1+\varepsilon)n$ for all $w\in V(G)\setminus\\{x,y\\}$.

  4. (d)

$G$ is a star-multigraph and $G$ has two distinct vertices $y,z$ such that

    1. (i)

$\mu(x)<\eta n$;

    2. (ii)

$d_{G}(y)=d_{G}(z)=\delta(G)\geq(\frac{1}{2}+\frac{3\varepsilon}{2})n$ and
$\min\\{d^{s}_{G}(y),d_{G}^{s}(z)\\}>\Delta(G)-\frac{1}{2}(1-0.9\varepsilon)n$;
and

    3. (iii)

$d_{G}(w)=\Delta(G)\geq(1+\varepsilon)n$ and
$d_{G}^{s}(w)\geq(1+\varepsilon)n-\mu(x)\geq(1+0.9\varepsilon)n$ for all $w\in
V(G)\setminus\\{y,z\\}$.

  5. (e)

$G$ is a star-multigraph, $|U|\geq\eta n$,
$\delta(G)\geq\delta(G-x)\geq(1+\varepsilon)n$, and
$\mu(x)\leq\frac{2}{\eta}$.

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

Proof. We choose $n_{0}$ and $\eta$ so that
$0<\frac{1}{n_{0}}\ll\eta\ll\varepsilon$.

Let $x_{1}=x$, and $y_{1}\in V(G)\setminus\\{x\\}$. Define

$\displaystyle N^{b}(x)=$ $\displaystyle\emptyset$ Conditions (a), (d), and
(e);  $\displaystyle N^{b}(x)=$ $\displaystyle\\{v\in
V(G)\setminus\\{y_{1}\\}:e_{G}(x,v)\geq\eta n\\}$ Condition (b);
$\displaystyle N^{b}(x)=$ $\displaystyle N_{G}(x)\setminus\\{y_{1}\\}$
Condition (c).

We then define a set $N$ according to the different conditions as follows:

  1. Condition (a): let $N=\\{x_{1},y_{1}\\}$.

  2. Condition (b): let $N^{b}(x)=\\{x_{2},\ldots,x_{t}\\}$. By the assumption of Condition (b), we have $t-1<n^{\frac{1}{2}}$. We take distinct $y_{2},\ldots,y_{t}\in V(G)\setminus\\{x_{1},y_{1},x_{2},\ldots,x_{t}\\}$ and define $N=\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}$.

  3. Condition (c): let $N_{G}(x)\setminus\\{y_{1}\\}=\\{x_{2},\ldots,x_{t}\\}$. By the assumption of Condition (c), we have $t-1<n^{\frac{1}{2}}$. We take distinct $y_{2},\ldots,y_{t}\in V(G)\setminus\\{x_{1},y_{1},x_{2},\ldots,x_{t}\\}$ and define $N=\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}$.

  4. Condition (d): let $N=\\{x_{1},y_{1},x_{2},y_{2}\\}$, where $x_{2}=y$ and $y_{2}=z$.

  5. Condition (e): take $2\lfloor(2n-|V_{\Delta}|)/2\rfloor$ vertices from $V(G)\setminus V_{\Delta}$ and name them as $x_{2},y_{2},\ldots,x_{t},y_{t}$, where $t-1:=\lfloor(2n-|V_{\Delta}|)/2\rfloor$ and we assume that the first $\lfloor|U|/2\rfloor$ pairs of vertices $x_{i},y_{i}$ are all from $U$. Let $N=\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}$.

We say that $y_{i}$ and $x_{i}$ from the set $N$ are _partners_ of each other.

Applying Lemma 4.1 on the underlying graph of $G$ and $N$, we obtain a
partition $\\{A,B\\}$ of $V(G)$ satisfying the following properties in the
underlying graph of $G$: $|A|=|B|$; $|A\cap\\{x_{i},y_{i}\\}|=1$ for each
$i\in[1,t]$; and $|d_{A}(v)-d_{B}(v)|\leq n^{\frac{2}{3}}-1$ for each $v\in
V(G)$.

For the pair $(x_{1},y_{1})$, where recall $x_{1}=x$, by switching the two
vertices from their current partitions and renaming the resulting partitions
if necessary, we may assume that $x\in A$ and $d_{B}(x)\geq d_{A}(x)$. When
$G$ is in Conditions (b) or (c), if $N^{b}(x)\cap A\neq\emptyset$, we move
vertices in $N^{b}(x)\cap A$ from $A$ to $B$ and move the partners of vertices
in $N^{b}(x)\cap A$ from $B$ to $A$. Still denote by $A$ and $B$ the resulting
partition of $V(G)$. Then we still have $d_{B}(x)\geq d_{A}(x)$ as
$e_{G}(x,x_{i})\geq e_{G}(x,y_{i})$ for any $x_{i}\in N^{b}(x)$. Considering
now the partition $\\{A,B\\}$ in the multigraph $G$, it has the properties
below, where “Pa” indicates the property when $G$ is in Condition (a), and
similar meaning for “Pb” to “Pe.”

  1. Pa

$\displaystyle|d_{A}(v)-d_{B}(v)|$ $\displaystyle\leq$ $\displaystyle
n^{\frac{2}{3}}+e_{G}(x,v)\quad\text{for each $v\in V(G)\setminus\\{x\\}$.}$

  2. Pb

$\displaystyle N^{b}(x)$ $\displaystyle\subseteq$ $\displaystyle B;$
$\displaystyle|d_{A}(v)-d_{B}(v)|$ $\displaystyle\leq$ $\displaystyle
n^{\frac{2}{3}}+2n^{\frac{1}{2}}+n^{\frac{1}{2}}+e_{G}(x,v)\quad\text{for each
$v\in V(G)\setminus\\{x\\}$,}$

where the term “$n^{\frac{1}{2}}$” is to take account the the possible number
of multiple edges joining $x$ and $z$.

  3. Pc

$\displaystyle N_{G}(x)$ $\displaystyle\subseteq$ $\displaystyle B;$
$\displaystyle|d_{A}(v)-d_{B}(v)|$ $\displaystyle\leq$ $\displaystyle
n^{\frac{2}{3}}+2n^{\frac{1}{2}}+e_{G}(x,v)\quad\text{for each $v\in
V(G)\setminus\\{x\\}$.}$

  4. Pd

$\displaystyle|\\{y,z\\}\cap A|$ $\displaystyle=$ $\displaystyle|\\{y,z\\}\cap
B|=1;$ $\displaystyle|d_{A}(v)-d_{B}(v)|$ $\displaystyle\leq$ $\displaystyle
n^{\frac{2}{3}}+e_{G}(x,v)\quad\text{for each $v\in V(G)\setminus\\{x\\}$.}$

  5. Pe

$\displaystyle|U\cap A|\geq\lfloor\frac{|U|}{2}\rfloor,$ $\displaystyle|U\cap
B|\geq\lfloor\frac{|U|}{2}\rfloor;$ $\displaystyle|d_{A}(v)-d_{B}(v)|$
$\displaystyle\leq$ $\displaystyle n^{\frac{2}{3}}+e_{G}(x,v)\quad\text{for
each $v\in V(G)\setminus\\{x\\}$.}$

Let

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

Define $G_{A,B}$ to be the union of $G[A]$, $G[B]$ together with
$\lfloor(d_{B}(x)-d_{A}(x))/2\rfloor$ edges incident with $x$ from $E(H)$.
When $G$ is in Conditions (b) or (c), we take at most $\lceil
e_{G}(x,u)/2\rceil$ edges between $x$ and each $u\in B$. In particular, when
$G$ is in Conditions (c), as $N_{G}(x)\subseteq B$, we take either $\lfloor
e_{G}(x,u)/2\rfloor$ or $\lceil e_{G}(x,u)/2\rceil$ edges between $x$ and each
$u\in N_{G}(x)$. By this definition of $G_{A,B}$ and the Properties Pa to Pe
above, we have

$\displaystyle d_{G_{A,B}}(x)$ $\displaystyle=$ $\displaystyle\lfloor
d_{G}(x)/2\rfloor,$ $\displaystyle d_{G_{A,B}}(v)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(d_{G}(v)-e_{G}(v,x)-n^{\frac{2}{3}}-2n^{\frac{1}{2}}-n^{\frac{1}{2}}\right)+e_{G}(v,x)\quad\text{for
$v\in A\setminus\\{x\\}$,}$ (1) $\displaystyle d_{G_{A,B}}(v)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(d_{G}(v)-e_{G}(v,x)-n^{\frac{2}{3}}-2n^{\frac{1}{2}}-n^{\frac{1}{2}}\right)\quad\text{for
$v\in B$.}$

For vertex $v\in V(G)\setminus(N_{b}(x)\cup\\{x\\})$, as $e_{G}(x,v)<\eta n$
when $G$ is in Conditions (a) to (d) and $e_{G}(x,v)\leq\frac{2}{\eta}$ when
$G$ is in Condition (e), we will use the following bound:

$\displaystyle d_{G_{A,B}}(v)\geq$
$\displaystyle\frac{1}{2}\left(d_{G}(v)-1.2\eta n\right)$ when $G$ is in
Conditions (a) to (d); $\displaystyle d_{G_{A,B}}(v)\geq$ (2) $\displaystyle
d_{G_{A,B}}(v)\geq$
$\displaystyle\frac{1}{2}\left(d_{G}(v)-2n^{\frac{2}{3}}\right)$ when $G$ is
in Condition (e).

For $v\in N^{b}(x)$, we have

$d_{G_{A,B}}(v)\geq\frac{1}{2}\left(d^{s}_{G}(v)-2n^{\frac{2}{3}}\right).$ (3)

Furthermore, when $G$ is in Conditions (a) to (d), by the assumptions on $G$
and the partition $\\{A,B\\}$, we have $\sum_{v\in A}d_{G}(v)=\sum_{v\in
B}d_{G}(v)$ and so $e(G_{A})=e(G_{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
updated step by step.

  1. Step 1

Define $S=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq 7n^{\frac{2}{3}}\\}$. Let
$k=\Delta(G_{A,B})+\lfloor n^{\frac{1}{2}}\rfloor$. Since $G$ is a near star-
multigraph with $\mu(G-x)<n^{\frac{1}{2}}$, by Theorem 2.14, we find an edge
$k$-coloring $\varphi$ of $G_{A,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},G_{B}$ and
$G_{A,B}$, respectively, as $G_{A}^{*}$, $G_{B}^{*}$, and $G^{*}_{A,B}$, and
call $G^{*}$ the union of $G^{*}_{A,B}$ and $H$. It can be verified that
$\Delta(G^{*})=\Delta(G)$. We will modify the current edge coloring, which is
still named $\varphi$, such that the following properties are satisfied:

    1. S1.1

Let $i,j\in[1,k]$ and $C\in\\{A,B\\}$. When $G$ is in Conditions (a) to (d),
we have

$|\overline{\varphi}^{-1}_{A}(i)|=|\overline{\varphi}^{-1}_{B}(i)|\quad\text{and}\quad||\overline{\varphi}^{-1}_{C}(i)|-|\overline{\varphi}^{-1}_{C}(j)||\leq
2\quad$

When $G$ is in Condition (e), we have

$\left||\overline{\varphi}_{C}^{-1}(i)|-|\overline{\varphi}_{C}^{-1}(j)|\right|\leq
2.$

    2. S1.2

Let $i\in[1,k]$. When $G$ is in Conditions (a) to (d), we have

$|\overline{\varphi}^{-1}_{A}(i)|<3\eta
n\quad\text{and}\quad|\overline{\varphi}^{-1}_{B}(i)|<3\eta n.$

When $G$ is in Condition (e), we have

$|\overline{\varphi}^{-1}_{A}(i)|<7n^{\frac{2}{3}}\quad\text{and}\quad|\overline{\varphi}^{-1}_{B}(i)|<7n^{\frac{2}{3}}.$

  2. Step 2

Modify the partial edge-coloring of $G^{*}$ obtained in Step 1 by exchanging
alternating paths. Upon the completion of Step 2, each of the $k$ color class
will be a 1-factor of $G^{*}$. In the process of Step 2, a few edges of $H$
will be colored and a few edges of $G^{*}_{A}\cup 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, three,
or four edges will be added to at least one of them when each time we exchange
an alternating path. The calculations involved when $G$ is in Condition (e) is
essentially different than the other cases, so we need define parameters
correspondingly as follows: let

$\displaystyle s=$ $\displaystyle 3\eta n^{2}$ when $G$ is in Conditions (a)
to (d),  $\displaystyle s=$ $\displaystyle 7n^{\frac{5}{3}}$ when $G$ is in
Condition (e),

and

$\displaystyle r=$ $\displaystyle\eta^{\frac{1}{2}}n$ when $G$ is in
Conditions (a) to (d),  $\displaystyle r=$ $\displaystyle n^{\frac{5}{6}}$
when $G$ is in Condition (e).

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 $4s$. When $G$ is in Conditions (a) to (d), $G_{A}^{*}$ and $G_{B}^{*}$
have the same number of uncolored edges; and when $G$ is in Condition (e), the
number of uncolored edges in $G_{B}^{*}$ is greater than or equal to the
number of uncolored edges in $G_{A}^{*}$ (this follows if we assume by
symmetry that $e(G_{A}^{*})\leq e(G_{B}^{*})$).

    2. S2.2

$\Delta(R_{A})$ and $\Delta(R_{B})$ are less than $r$.

    3. S2.3

For $C\in\\{A,B\\}$, let $S_{C}=\\{u\in S\cap C\,:\,d_{G_{A,B}^{*}}(u)\leq
k-2n^{\frac{2}{3}}\\}.$ We require every vertex $u\in
V(G^{*})\setminus(S_{A}\cup S_{B}\cup N^{b}(x)\cup\\{x\\})$ is incident in
$G^{*}$ with fewer than $|\overline{\varphi}(u)|+r$ colored edges of $H$; and
every vertex $u\in S_{A}\cup S_{B}\cup N^{b}(x)\cup\\{x\\}$ is incident in
$G^{*}$ with at most $|\overline{\varphi}(u)|$ colored edges of $H$.

  3. Step 3

We will edge color each of $R_{A}$ and $R_{B}$ and color a few uncolored edges
of $H$ using another $\ell$ colors, where $\ell=2\lfloor r\rfloor$. 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 U$ 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. We
will show that $\Delta(R)=\Delta(G^{*})-k-\ell$. This submultigraph is
bipartite, so we can color its edges using $\Delta(G^{*})-k-\ell$ colors by
Theorem 2.9.

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 notation
that was already defined in the outline above, we will use them directly.

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

Recall $S=\\{v\in V(G)\,:\,\Delta(G)-d_{G}(v)\geq 7n^{\frac{2}{3}}\\}$. Note
that when $G$ is in Conditions (a) to (c), $S=\emptyset$; when $G$ is in
Condition (d), $S\subseteq\\{y,z\\}$; and when $G$ is in Condition (e),
$U\subseteq S$. When $G$ is in Condition (d), we have $|\\{y,z\\}\cap
A|=|\\{y,z\\}\cap B|=1$ by Property Pd. Thus, when $G$ is in Conditions (a) to
(d), we have $G_{A}^{*}=G_{A}$, $G_{B}^{*}=G_{B}$, $G_{A,B}^{*}=G_{A,B}$, and
$G^{*}=G$.

Following the operations described in the outline of Step 1, for the current
edge coloring $\varphi$ of $G_{A,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, for
any $C\in\\{A,B\\}$, we have

$\sum_{u\in C\cap S}|\overline{\varphi}(u)|=\sum_{u\in C\cap
S}(k-d_{G^{*}_{A,B}}(u))\leq k.$ (4)

Note that $k\leq\Delta(G_{A,B})+n^{\frac{1}{2}}$, and by the partition
$\\{A,B\\}$ of $V(G)$, we have $\Delta(G_{A,B})\leq\max_{v\in
V(G)}\\{\frac{1}{2}\left(\Delta(G)-e_{G}(x,v)+n^{\frac{2}{3}}+2n^{\frac{1}{2}}+n^{\frac{1}{2}}\right)+e^{*}\\}$,
where $e^{*}=e_{G}(x,v)<\eta n$ if $v\in A$ and $e^{*}=\lceil
e_{G}(x,v)/2\rceil$ if $v\in B$. Thus when $G$ is in Conditions (a) to (d), we
have

$k\leq\frac{1}{2}\left(\Delta(G)+n^{\frac{2}{3}}+2n^{\frac{1}{2}}+n^{\frac{1}{2}}\right)+\frac{1}{2}\eta
n+n^{\frac{1}{2}}<\frac{1}{2}\Delta(G)+0.6\eta n.$ (5)

When $G$ is in Condition (e), as $\mu(G)<\frac{2}{\eta}$, we have

$k\leq\frac{1}{2}\left(\Delta(G)+n^{\frac{2}{3}}+2n^{\frac{1}{2}}+n^{\frac{1}{2}}\right)+\frac{1}{\eta}+n^{\frac{1}{2}}<\frac{1}{2}\Delta(G)+n^{\frac{2}{3}}.$
(6)

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)$. To see $\Delta(G^{*})=\Delta(G)$, note
that the edge additions in Step 1 happen only when $G$ is in Condition (e).
Under Condition (e), 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^{\frac{2}{3}}++\frac{1}{2}(\Delta(G)-7n^{\frac{2}{3}}+n^{\frac{2}{3}}+\frac{2}{\eta})<\Delta(G).$

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

$d_{G^{*}}(u)\leq\frac{1}{2}\Delta(G)+n^{\frac{2}{3}}+\frac{1}{2}(\Delta(G)-\eta
n+n^{\frac{2}{3}}+\frac{2}{\eta})<\Delta(G)-\frac{\eta n}{3}.$ (7)

When $G$ is in Conditions (a) to (d), since
$e(G_{A}^{*})=e(G_{A})=e(G_{B})=e(G_{B}^{*})$, by Lemma 2.11, we modify
$\varphi$ into an edge $k$-coloring of $G^{*}_{A,B}$, and still call $\varphi$
the resulting coloring, such that

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

When $G$ is in Condition (e), by Lemma 2.12, we modify $\varphi$ so that

$||\overline{\varphi}^{-1}_{C}(i)|-|\overline{\varphi}^{-1}_{C}(j)||\leq
2\quad\text{for $i,j\in[1,k]$ and $C\in\\{A,B\\}$}.$

Note that under the modified coloring $\varphi$, 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 (4) still hold. For $C\in\\{A,B\\}$, define

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

Next, we verify that every color $i\in[1,k]$ is missing at a small number of
vertices. We first provide an upper bound on $|\overline{\varphi}(u)|$ for
each $u\in V(G^{*})$. By the definition of $G_{A,B}$, (LABEL:eqn:general-
degree-v-in-Gab), (3), (5), and (6), as
$|\overline{\varphi}(u)|=k-d_{G^{*}_{A,B}}(u)$, we have

Since $|\overline{\varphi}(u)|<2n$ for each $u\in N^{b}(x)$ and
$|N^{b}(x)|<n^{\frac{1}{2}}$, the inequalities above together with the fact in
(4) give the following inequalities for any $C\in\\{A,B\\}$:

$\displaystyle\sum\limits_{u\in C}|\overline{\varphi}(u)|$ $\displaystyle\leq$
$\displaystyle 2nn^{\frac{1}{2}}+2\eta n^{2}+k<3\eta n^{2}-2n\quad\text{$G$ is
in Conditions~{}\eqref{Ca} to~{}\eqref{Cd};}$ (13)
$\displaystyle\sum\limits_{u\in C}|\overline{\varphi}(u)|$ $\displaystyle\leq$
$\displaystyle
2nn^{\frac{1}{2}}+6n^{\frac{5}{3}}+k<7n^{\frac{5}{3}}-2n\quad\text{$G$ is in
Condition~{}\eqref{Ce}.}$ (14)

By SI.1, the Statement S1.2 stated in the outline of Step 1 holds.

Step 2: Extending existing color classes into 1-factors

We will extend each of the $k$ color classes obtained in Step 1 into a
1-factor of $G^{*}$ by exchanging alternating paths. Each alternating path
starts and also ends at an uncolored edge of $H$ and is alternating between
colored edges of $G_{A}^{*}\cup G_{B}^{*}$ and uncolored edges of $H$. Thus
during the procedure of Step 2, we will uncolor some of the edges of
$G^{*}_{A}\cup 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 initially empty.

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 $r$ (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}_{A}(i)$ and a vertex from
$\overline{\varphi}^{-1}_{B}(i)$, and then pair up the remaining unpaired
vertices from $\overline{\varphi}^{-1}_{A}(i)$ or
$\overline{\varphi}^{-1}_{B}(i)$ as
$|\overline{\varphi}^{-1}_{A}(i)|-|\overline{\varphi}^{-1}_{B}(i)|$ is even by
the Parity Lemma. 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) to (d), 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 13 edges, where,
if exist, the first, third, fifth, seventh, ninth, eleventh, and thirteenth
edges are uncolored and the second, fourth, sixth, eighth, tenth, and twelfth
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 four 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 (13) and (14), the total number of missing
colors from vertices in $A$ or from vertices in $B$ is at most $s$, which is
$3\eta n^{2}$ when $G$ is in Conditions (a) to (d), and is $7n^{\frac{5}{3}}$
when $G$ is in Condition (e). Thus there are at most $s$ MCC-pairs. For each
MCC-pair $(a,b)$ with $a,b\in V(G^{*})$, at most four 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 $4s$ edges in each of $R_{A}$ and
$R_{B}$. At the completion of Step 2, each of the $k$ color classes is a
1-factor of $G^{*}$ so each of $G_{A}^{*}$ and $G_{B}^{*}$ have the same
number of colored edges. When $G$ is in Conditions (a) to (d), since
$e(G_{A}^{*})=e(G_{A})=e(G_{B})=e(G_{B}^{*})$, we have $e(R_{A})=e(R_{B})$.
When $G$ is in Condition (e), suppose, without loss of generality, that
$e(G_{B}^{*})\geq e(G_{A}^{*})$, then we get $e(R_{B})\geq e(R_{A})$. 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 that

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

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

$|S_{A}|<n^{1/3}\quad\text{and}\quad|S_{B}|<n^{1/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}\cup
N^{b}(x)\cup\\{x\\})$ 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. 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 $r$. Hence the number of colored edges of $H$ that are incident with
$u$ will be less than $|\overline{\varphi}(u)|+r$. The number of newly colored
edges of $H$ that are incident with a vertex $u\in S_{A}\cup S_{B}\cup
N^{b}(x)\cup\\{x\\}$ will equal the number of colors that missed at $u$ at the
end of Step 1. Thus Condition S2.3 will be satisfied.

As the vertex $x$ may have a quite small simple degree, we deal with colors in
$\overline{\varphi}(x)$ first. By the upper bound on $|\overline{\varphi}(x)|$
given in Step 1, we have $|\overline{\varphi}(x)|<\eta n$ when $G$ is in
Conditions (a) to (d), and
$|\overline{\varphi}(x)|\leq\frac{1}{2}(1-\varepsilon)n+n^{\frac{2}{3}}$ when
$G$ is in Condition (e). When $G$ is in Condition (e), as
$\mu(G)\leq\frac{2}{\eta}$ and
$e_{G}(x,B)-e_{G_{A,B}^{*}}(x,B)\geq\frac{n}{2}$, we know that $x$ is adjacent
in $G$ with at least $\frac{n/2}{2/\eta}\geq\frac{\eta}{4}n$ vertices from $B$
that each joins $x$ with an uncolored edge of $H$.

For each $i\in\overline{\varphi}(x)$, if there is a vertex $w\in N_{G}(x,B)$
with $xw$ uncolored and $i\in\overline{\varphi}(w)$, we simply color $xw$ by
the color $i$. Thus we assume that for every $w\in N_{G}(x,B)$ with $xw$
uncolored, it holds that $i\not\in\overline{\varphi}(w)$. We choose $w\in
N_{G}(x,B)$ with $xw$ uncolored and with $d_{R_{B}}(w)$ smallest. Let
$w^{*}\in N_{G}(w,B)$ such that $ww^{*}$ is colored by $i$ (the vertex $w^{*}$
exists as we only added colored edges between $x$ and $N_{G}(x,B)$ so far and
$i\in\varphi(w)$). Then we color $xw$ by $i$ and uncolor $ww^{*}$. (We say
$w^{*}$ is _originated_ from $x$ with respect to the color $i$). This
procedure guarantees all edges of $R_{B}$ to be good, as when $G$ is in
Conditions (a) to (d), we have $|\overline{\varphi}(x)|<\eta
n<\eta^{\frac{1}{2}}n$; and when $G$ is in Condition (e), although
$|\overline{\varphi}(x)|\leq\frac{1}{2}(1-\varepsilon)n+n^{\frac{2}{3}}$, we
have at least $\frac{1}{4}\eta n-|\overline{\varphi}(x)|/n^{\frac{5}{6}}>1$
choices each time to pick a desired vertex $w\in N_{G}(x,B)$. After this
procedure, all the $k$ colors present at $x$. Thus $x$ is not contained in any
MCC-pair with respect to the current edge coloring.

Let $S^{*}_{A}=S_{A}\cup\\{x\\}$ and $S_{B}^{*}=S_{B}\cup N^{b}(x)$. We now
show below the existence of alternating paths for the current 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$ contain 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 $4s$ edges in $R_{B}$, so there are fewer than
$\frac{8s}{r}$ vertices of degree at least $r$ 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 $\frac{16s}{r}$ vertices in $B$ that are incident with a
non-good edge colored $i$. Furthermore, there are at most $2|S^{*}_{B}|\leq
3n^{\frac{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 $\max\\{3\eta n,7n^{\frac{2}{3}}\\}=3\eta n$ vertices in
$B$ that are missed by the color $i$ by S1.2. 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

$\frac{16s}{r}+3n^{\frac{1}{3}}+3\eta n<49\eta^{\frac{1}{2}}n.$

Similarly, 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 $49\eta^{\frac{1}{2}}n$. Note that, by the partition
$\\{A,B\\}$ of $V(G)$, we have

$\displaystyle|N_{G}(v,B)|$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(d^{s}_{G}(v)-n^{\frac{2}{3}}-2n^{\frac{1}{2}}-n^{\frac{1}{2}})\quad\text{for
$v\in A\setminus\\{x\\}$};$ $\displaystyle>$
$\displaystyle\frac{1}{2}(d^{s}_{G}(v)-2n^{\frac{2}{3}})$
$\displaystyle|N_{G}(v,A)|$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(d^{s}_{G}(v)-n^{\frac{2}{3}}-2n^{\frac{1}{2}}-n^{\frac{1}{2}})\quad\text{
for $v\in B$}.$ $\displaystyle>$
$\displaystyle\frac{1}{2}(d^{s}_{G}(v)-2n^{\frac{2}{3}})$

By S2.3 and the upper bound on $|\overline{\varphi}(u)|$ for any $u\in
V(G^{*})$ provided in Step 1, we have the following lower bounds on
$|N_{B}(a)|$ and $|N_{A}(b)|$:

  1. When $\\{a,b\\}\cap(S^{*}_{A}\cup S^{*}_{B})=\emptyset$,

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

  2. When $G$ is in Conditions (b) or (c) and $\\{a,b\\}\cap N^{b}(x)\neq\emptyset$, we have

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

  3. When $G$ is in Condition (c) and $b=y$, we have

$|N_{A}(b)|\geq\frac{1}{2}\left(2\varepsilon n-2n^{\frac{2}{3}}\right)-\eta
n-49\eta^{\frac{1}{2}}n>\frac{3}{4}\varepsilon n.$ (18)

  4. When $G$ is in Condition (d) and $\\{a,b\\}\cap\\{y,z\\}\neq\emptyset$, we have

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

When $G$ is in Condition (e) and $\\{a,b\\}\cap(S^{*}_{A}\cup
S^{*}_{B})\neq\emptyset$, we have

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

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 unified 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 (16)-(20) 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 (16)-(20) 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 (16), we have
$|M_{B}(a^{*})|>(\frac{1}{2}+\frac{1}{5}\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 (16), we have
$|M_{B}(a)|,|M_{A}(b_{2}^{*})|>(\frac{1}{2}+\frac{1}{5}\varepsilon)n.$
Therefore, as each vertex $c\in M_{A}(b_{2}^{*})$ satisfies
$|N_{B}(c)|>(\frac{1}{2}+\frac{1}{5}\varepsilon)n$, we have $|N_{B}(c)\cap
M_{B}(a)|\geq\frac{2}{5}\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 edges
to each of $R_{A}$ and $R_{B}$ when we updated the original MCC-pair
corresponding to $(a,a^{*})$, where $a$ and $a^{*}$ could be originated from
some vertices $b_{1}^{\prime},b_{2}^{\prime}\in S_{B}^{*}$. Also, exactly one
of $b_{1}^{\prime}$ and $b_{2}^{\prime}$ could be originated from $x$ with
respect to the color $i$. Thus we added at most three edges to $R_{A}$ and at
most four edges to $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^{*})$. The maximum length of an alternating path combined from the three
procedures (dealing missing colors at $x$, dealing missing colors at vertices
from $S_{A}\cup S_{B}^{*}$, and dealing missing colors at vertices from
$V(G^{*})\setminus(S_{A}^{*}\cup S_{B}^{*})$) together is at most
$2+2+2+7=13$. By symmetry, we can deal with an MCC-pair $(b,b^{*})$ with
respect to $i$ such that $b,b^{*}\in B$ similarly as above.

Then we consider an MCC-pair $(a,b)$ with respect to $i$ such that $a\in A$
and $b\in B$. By (16), we have
$|M_{B}(a)|,|M_{A}(b)|>(\frac{1}{2}+\frac{1}{5}\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}{5}\varepsilon)n$ by (16), 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 one edge to $R_{A}$ and at most two edges to $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 $4s$ edges, and
$\Delta(R_{A}),\Delta(R_{B})<r$. Note that $R_{A}$ and $R_{B}$ might contain
parallel edges with endvertices in $S$ or between $y$ and $z$ when $G$ is in
Condition (d). By Theorem 2.8 and Theorem 2.10, $R_{A}$ and $R_{B}$ each has
an equalized edge-coloring with exactly $\ell:=2\lfloor r\rfloor$ colors
$k+1,\ldots,k+\ell$.

If $G$ is in Conditions (a) to (d), then we have $e(R_{A})=e(R_{B})$. Under
these 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 (e), 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 $4s$ edges in each of $R_{A}$ and $R_{B}$, and $\ell>r$,
so each of the color $i\in[k+1,k+\ell]$ appears on fewer than $\frac{4s}{r}$
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 U$. 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\times\frac{4s}{r}=\frac{8s}{r}$,
as $R_{A}$ and $R_{B}$ each contains fewer than $\frac{4s}{r}$ edges colored
$i$. Note that if $G$ is in Conditions (a) to (d), we have $|A_{i}|=|B_{i}|$;
and we might have $|B_{i}|>|A_{i}|$ when $G$ is in Condition (e). When $G$ is
in Condition (e) and $|B_{i}|>|A_{i}|$, we let

$A_{i}^{*}\subseteq(U\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 $|U\cap A|\geq\frac{1}{2}\eta
n-1$ and $|A_{i}|,|B_{i}|<\frac{8s}{r}=56n^{\frac{5}{6}}$. 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$.

For each $u\in V(G^{*})$, the number of colored edges of $H$ incident with $u$
is specified by S2.3 and at most $\ell$ edges incident with $u$ have been
colored in Step 3. Also each vertex in $G^{*}$ has fewer than
$\frac{8s}{r}<24\eta^{\frac{1}{2}}n$ edges that join it with a vertex in
$A_{i}$ or $B_{i}$. So by (LABEL:eqn:v_H-degree), each vertex $u\in
V(H_{i})\setminus(S^{*}_{A}\cup S^{*}_{B})$ satisfies

$d_{H_{i}}^{s}(u)>\frac{1}{2}\left((1+\frac{1}{2}\varepsilon)n-2n^{\frac{2}{3}}\right)-(2\eta
n+\eta^{\frac{1}{2}}n)-\ell-24\eta^{\frac{1}{2}}n>(\frac{1}{2}+\frac{\varepsilon}{5})n.$

Note that $V(R_{A}\cup R_{B})\cap(S_{A}^{*}\cup S_{B}^{*})=\emptyset$. When
$G$ is in Conditions (b) or (c), each of the vertex $u\in N^{b}(x)$, where
$u\neq y$ when $G$ is in Condition (c), satisfies

$d_{H_{i}}^{s}(u)>\frac{1}{2}\left((1+\varepsilon)n-2n^{\frac{2}{3}}\right)-(\frac{1}{2}-\frac{1}{3}\varepsilon)n-\ell-24\eta^{\frac{1}{2}}n>\frac{1}{2}\varepsilon
n.$

When $G$ is in Condition (c), the vertex $y$ satisfies

$d_{H_{i}}^{s}(y)>\frac{1}{2}\left(2\varepsilon n-2n^{\frac{2}{3}}\right)-\eta
n-\ell-24\eta^{\frac{1}{2}}n>\frac{\varepsilon}{4}\varepsilon n.$

When $G$ is in Condition (d), each $u\in\\{y,z\\}$ satisfies

$d_{H_{i}}^{s}(u)>\frac{1}{2}\left((\frac{1}{2}+\frac{3\varepsilon}{2})n-\eta
n-2n^{\frac{2}{3}}\right)-(\frac{1}{4}-\frac{1}{5}\varepsilon)n-\ell-24\eta^{\frac{1}{2}}n>\frac{3}{4}\varepsilon
n.$

When $G$ is in Condition (e), each $u\in S_{A}\cup S_{B}$ satisfies

$d_{H_{i}}^{s}(u)>\frac{1}{2}\left((1+\varepsilon)n-2n^{\frac{2}{3}}\right)-(\frac{1}{2}-\frac{1}{3}\varepsilon)n-\ell-24\eta^{\frac{1}{2}}n>\frac{1}{2}\varepsilon
n.$

For the vertex $x$, we have

$d_{H_{i}}(x)\geq\delta(G)-k-\ell-24\eta^{\frac{1}{2}}n\geq(1+\varepsilon)n-\left(\frac{1}{2}\Delta(G)+0.6\eta
n\right)-\ell-24\eta^{\frac{1}{2}}n>\frac{1}{2}\varepsilon n.$

Thus $\delta(H_{i})\geq 1$ and $\delta(H_{i}-x)\geq\frac{1}{2}\varepsilon n-1$
in any case and $H_{i}$ has at most $|S^{*}_{A}\cup S^{*}_{B}|\leq
3n^{1/3}<\frac{1}{2}\varepsilon n-1$ vertices of simple degree less than
$\frac{1}{2}n+1$. So $H_{i}$ has a 1-factor $F$ by Lemma 2.6. 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 U$. 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
U$.

Step 4: Coloring the graph $R$

Let $R$ be the submultigraph of $G^{*}$ consisting of the remaining uncolored
edges. These edges all belong to $H$, so $R$ is a submultigraph of $H$ and
hence is bipartite. We claim that $\Delta(R)=\Delta(G^{*})-k-\ell$. This is
obvious when $G$ is in Conditions (a) to (d). Thus we assume that $G$ is in
Condition (e). Note that every vertex from $V(G^{*})\setminus U$ presents
every color from $[1,k+\ell]$ and so those vertices have degree at most
$\Delta(G^{*})-k-\ell$ in $R$. For some vertices from $U$, they present all
the colors from $[1,k]$. Thus by (7), those vertices have degree at most

$\Delta(G^{*})-\frac{1}{3}\eta
n-k<\Delta(G^{*})-k-\ell=\Delta(G^{*})-k-2\lfloor n^{\frac{5}{6}}\rfloor$

in $R$. By Theorem 2.9 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.1, we can obtain a desired partition
$\\{A,B\\}$ of $V(G)$ in polynomial time. Also, it is polynomial time to edge
color $G_{A,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 the desired 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. [14])
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.10,
these edge colorings can be modified into equalized edge-colorings in
polynomial time. The last step is to edge color the bipartite multigraph $R$
using $\Delta(R)$ colors, which can be done in polynomial time in $n$, for
example, using an algorithm from [5]. Thus, there is a polynomial time
algorithm that gives an edge coloring of $G$ using $\Delta(G)$ colors. ∎

## References

  * [1] J. A. Bondy and U. S. R. Murty.  Graph theory with applications.  American Elsevier Publishing Co., Inc., New York, (Elsevier North-Holland), 1976.
  * [2] A. G. Chetwynd and A. J. W. Hilton.  $1$-factorizing regular graphs of high degree—an improved bound.  Discrete Math., 75(1-3): 103–112, 1989.
  * [3] 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.
  * [4] 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.
  * [5] R. Cole and J. Hopcroft.  On edge coloring bipartite graphs.  SIAM J. Comput., 11(3):540–546, 1982.
  * [6] 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.
  * [7] G. A. Dirac.  Some theorems on abstract graphs.  Proc. London Math. Soc. (3), 2:69–81, 1952.
  * [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] 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] J. E. Hopcroft, and R. M. Karp.  An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.  SIAM J. Comput., 2(4):225–231, 1973.
  * [14] H. J. Karloff and D. B. Shmoys.  Efficient parallel algorithms for edge coloring problems.  J. Algorithms, 8(1):39–52, 1987.
  * [15] D. König.  Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.  Math. Ann., 77(4):453–465, 1916.
  * [16] C. J. H. McDiarmid.  The solution of a timetabling problem.  J. Inst. Math. Appl., 9:23–34, 1972.
  * [17] J. Misra and D. Gries.  A constructive proof of Vizing’s theorem.  Inform. Process. Lett., 41(3):131–133, 1992.
  * [18] L. Perković and B. Reed.  Edge coloring regular graphs of high degree.  Discrete Math., 165/166: 567–578, 1997.
  * [19] M. Plantholt.  Overfull conjecture for graphs with high minimum degree.  J. Graph Theory, 47(2):73–80, 2004.
  * [20] M. Plantholt.  The chromatic index of graphs with large even order $n$ and minimum degree at least $2n/3$.  Discrete Math., 345(7): 112880, 2022.
  * [21] M. Plantholt and S. Shan.  Edge coloring graphs with large minimum degree.  arXiv:2105.05286, 2021.
  * [22] P. D. Seymour.  On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.  Proc. London Math. Soc. (3), 38(3):423–460, 1979.
  * [23] S. Shan.  Chromatic index of dense quasirandom graphs.  arXiv:2104.06253, 2021.
  * [24] M. Stiebitz, D. Scheide, B. Toft, and L. M. Favrholdt.  Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2012.
  * [25] V. G. Vizing.  Critical graphs with given chromatic class.  Diskret. Analiz No., 5:9–17, 1965.