# Chromatic index of dense quasirandom graphs

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|V(H)|/2\rfloor$.
Chetwynd and Hilton in 1985 conjectured that a graph $G$ on $n$ vertices with
$\Delta(G)>n/3$ has chromatic index $\Delta(G)$ if and only if $G$ contains no
overfull subgraph. Glock, Kühn and Osthus in 2016 showed that the conjecture
is true for dense quasirandom graphs with even order, and they conjectured
that the same should hold for such graphs with odd order. In this paper, we
show that the conjecture of Glock, Kühn and Osthus is affirmative.

_Keywords._ Chromatic index; overfull graph; quasirandom graph.

##  1 Introduction

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

For two integers $p,q$, let $[p,q]=\\{i\in\mathbb{Z}\,:\,p\leq i\leq q\\}$. An
edge $k$-coloring of $G$ is a mapping $\varphi$ from $E(G)$ to the set of
integers $[1,k]$, called colors, such that no two adjacent edges receive the
same color with respect to $\varphi$. The chromatic index of $G$, denoted
$\chi^{\prime}(G)$, is defined to be the smallest integer $k$ so that $G$ has
an edge $k$-coloring. We denote by $\mathcal{C}^{k}(G)$ the set of all edge
$k$-colorings of $G$. A graph $G$ is _$\Delta$ -critical_ if
$\chi^{\prime}(G)=\Delta(G)+1=\Delta+1$ and $\chi^{\prime}(H)<\Delta+1$ for
every proper subgraph $H$ of $G$. In 1960’s, Vizing [22] and, independently,
Gupta [8] proved that for all simple graphs $G$,
$\Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1$. This leads to a natural
classification of graphs. Following Fiorini and Wilson [5], we say a graph $G$
is of class 1 if $\chi^{\prime}(G)=\Delta(G)$ and of _class 2_ if
$\chi^{\prime}(G)=\Delta(G)+1$. Holyer [10] showed that it is NP-complete to
determine whether an arbitrary graph is of class 1. Nevertheless, if a graph
$G$ has too many edges, i.e., $|E(G)|>\Delta(G)\lfloor|V(G)|/2\rfloor$, then
we have to color $E(G)$ using exactly $(\Delta(G)+1)$ colors. Such graphs are
_overfull_. An overfull subgraph $H$ of $G$ with $\Delta(H)=\Delta(G)$ is
called a _$\Delta(G)$ -overfull subgraph_ of $G$.

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

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

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

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

Recently in 2016, Glock, Kühn and Osthus [6] showed that the overfull
conjecture is true for dense quasirandom graphs of even order. Following their
definition, for the notion of quasirandomness, the following one-sided version
of $\varepsilon$-regularity will be considered. Let $0<\varepsilon,p<1$. A
graph $G$ on $n$ vertices is called _lower- $(p,\varepsilon)$-regular_ if we
have $e_{G}(S,T)\geq(p-\varepsilon)|S||T|$ for all disjoint $S,T\subseteq
V(G)$ with $|S|,|T|\geq\varepsilon n$. In particular, the following result was
proved in [6, Theorem 1.6].

######  Theorem 1.2.

For all $0<p<1$ there exist $\varepsilon,\eta>0$ such that for sufficiently
large $n$, the following holds: Suppose $G$ is a
lower-$(p,\varepsilon)$-regular graph on $n$ vertices and $n$ is even.
Moreover, assume that $\Delta(G)-\delta(G)\leq\eta n$. Then
$\chi^{\prime}(G)=\Delta(G)$ if and only if $G$ contains no
$\Delta(G)$-overfull subgraph. Further, there is a polynomial time algorithm
which finds an optimal coloring.

Glock, Kühn and Osthus [6] conjectured that the same result as in Theorem 1.2
should hold for such graphs $G$ with odd order. We here confirm the
conjecture.

######  Theorem 1.3.

For all $0<p<1$ there exist $\varepsilon,\eta>0$ such that for sufficiently
large $n$, the following holds: Suppose $G$ is a
lower-$(p,\varepsilon)$-regular graph on $n$ vertices and $n$ is odd.
Moreover, assume that $\Delta(G)-\delta(G)\leq\eta n$. Then
$\chi^{\prime}(G)=\Delta(G)$ if and only if $G$ is not overfull. Further,
there is a polynomial time algorithm which finds an optimal coloring.

For a lower-$(p,\varepsilon)$-regular graph with odd order $n$, it is easy to
see that for any subset $X\subseteq V(G)$ with $|X|$ odd and $3\leq|X|\leq
n-2$, we have $e_{G}(X,V(G)\setminus X)\geq\Delta(G)$. Thus $G[X]$ is not
$\Delta(G)$-overfull. Therefore, the only possible $\Delta(G)$-overfull
subgraph in $G$ is $G$ itself.

The remainder of this paper is organized as follows. In the next section, we
list some preliminary results on quasirandom graphs and edge colorings. In
Section 3, we study the chromatic index of a regular
lower-$(p,\varepsilon)$-regular star-multigraph, which is obtained from a
lower-$(p,\varepsilon)$-regular graph by adding a new vertex and some edges
between the graph and the new vertex. In the last section, we prove Theorem
1.3.

##  2 Preliminaries

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

###  2.1 Properties of lower-$(p,\varepsilon)$-regular graphs

A lower-$(p,\varepsilon)$-regular graph can be slightly modified so it is
still lower-$(p,\varepsilon^{\prime})$-regular for some
$\varepsilon^{\prime}\leq\varepsilon$, as listed in the following proposition.

######  Proposition 2.1 ([6], Proposition 3.1).

Let $0<1/n_{0}\ll\varepsilon,p<1$, and let $G$ be a
lower-$(p,\varepsilon)$-regular graph on $n\geq n_{0}$ vertices. Then the
following hold:

  1. (1)

If $G^{\prime}$ is obtained from $G$ by adding a new vertex $w$ and arbitrary
edges at $w$, then $G^{\prime}$ is lower-$(p,2\varepsilon)$-regular.

  2. (2)

Let $H$ be a graph on $V(G)$ such that $\Delta(H)\leq\eta n$. Let
$\varepsilon^{\prime}=\max\\{2\varepsilon,2\sqrt{\eta}\\}$. Then $G-E(H)$ is
lower-$(p,\varepsilon^{\prime})$-regular.

  3. (3)

If $U\subseteq V(G)$ has size at least $\beta n$, then $G[U]$ is
lower-$(p,\varepsilon/\beta)$-regular.

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$. For
$0<\varepsilon,p<1$, a multigraph $G$ is a lower-$(p,\varepsilon)$-regular
_star-multigraph_ graph if it is a star-multigraph such that its underlying
simple graph is lower-$(p,\varepsilon)$-regular. Since we will deal with a
lower-$(p,\varepsilon)$-regular graph of odd order, for convenient analyses,
we will add a new vertex and some edges between the new vertex and the graph
to form a star-multigraph of even order.

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

The following result was proved in [6] for lower-$(p,\varepsilon)$-regular
graphs, and we here modify it for lower-$(p,\varepsilon)$-regular star-
multigraphs.

######  Lemma 2.2 ([6], Lemma 7.2).

Let $0<1/n_{0}\ll\varepsilon\ll\alpha,p<1$, and $G$ be a
lower-$(p,\varepsilon)$-regular graph on $n\geq n_{0}$ vertices such that
$\delta(G)\geq\alpha 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 $\alpha n/5$.
Then there exist vertex-disjoint path $P_{1},\ldots,P_{t}$ in $G$ such that
$\bigcup V(P_{i})=V(G)$ and $P_{i}$ joins $a_{i}$ to $b_{i}$, and these paths
can be found in polynomial time.

######  Lemma 2.3.

Let $0<1/n_{0}\ll\varepsilon\leq\eta\ll\alpha,p<1$, and $G$ be a
lower-$(p,\varepsilon)$-regular star-multigraph on $n\geq n_{0}$ vertices such
that $\delta(G)\geq\alpha n$ and $e_{G}(x,v)\leq\eta n$ for any $v\in V(G)$,
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 $\alpha n/6$. 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_{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(\alpha-\eta)n\geq(\frac{5}{6}\alpha+\frac{5}{n})n$ and
$|M^{\prime}|\leq\frac{1}{6}\alpha n+1=(\frac{1}{6}\alpha+\frac{1}{n})n$, and
$G-x$ is lower-$(p,2\varepsilon)$-regular by Proposition 2.1 (3). Applying
Lemma 2.2 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.2 and the simple adjustment on $M$ above, it is clear that
these paths can be found also in polynomial time. ∎

######  Lemma 2.4.

Let $0<1/n_{0}\ll\varepsilon,\gamma\ll\alpha,p<1$, and $G$ be a
lower-$(p,\varepsilon)$-regular star-multigraph on $n\geq n_{0}$ vertices such
that $\delta(G)\geq\alpha n$. Let $X,Y\subseteq V(G)$ be disjoint and
$|X|=|Y|$, and $H$ be a graph with $V(H)=X\cup Y$ and $E(H)$ obtained from
$E_{G}(X,Y)$ by deleting some edges. If $\delta(H)>\frac{1}{4}\alpha n$ and
each vertex $v\in V(H)\setminus\\{x\\}$ is incident with at most $\gamma n$
edges from $E_{G}(X,Y)\setminus E(H)$, then $H$ has a perfect matching.
Furthermore, a perfect matching of $H$ can be found in polynomial time.

Proof. If the multi-center of $G$ is contained in $X\cup Y$, we may assume by
symmetry that the multi-center is contained in $X$. To have a uniform proof,
if the multi-center of $G$ is contained in $X$, we let $x$ be the multi-
center; otherwise we let $x$ be an arbitrary vertex from $X$.

Since $\delta(H)>0$, $x$ has in $H$ a neighbor $y\in Y$. Let
$X_{1}=X\setminus\\{x\\}$ and $Y_{1}=Y\setminus\\{y\\}$. It suffices to show
that $H_{1}:=H[X_{1},Y_{1}]$ satisfies Hall’s condition. For otherwise, there
exists $A\subseteq X_{1}$ such that $B:=N_{H_{1}}(A)$ satisfying $|B|<|A|$.
Since $\delta(H_{1})\geq\frac{1}{4}\alpha n-1$ and $|B|<|A|$, it follows that
$|A|>\frac{1}{4}\alpha n-1$. On the other hand, since
$E_{H_{1}}(A,Y_{1}\setminus B)=\emptyset$, $Y_{1}\setminus B\neq\emptyset$,
and $\delta(H_{1})\geq\frac{1}{4}\alpha n-1$, it follows that $|X_{1}\setminus
A|\geq\frac{1}{4}\alpha n-1$. Let $B_{1}=Y_{1}\setminus B$. Thus
$|A|\leq|X_{1}|-(\frac{1}{4}\alpha n-1)$ and so
$|B_{1}|=|Y_{1}|-|B|>|Y_{1}|-|A|\geq\frac{1}{4}\alpha n-1$. Now
$|A|>\frac{1}{4}\alpha n-1>\varepsilon n$ and $|B_{1}|>\frac{1}{4}\alpha
n-1>\varepsilon n$. By the lower-$(p,\varepsilon)$-regularity of $G$,
$e_{G}(A,B_{1})\geq(p-\varepsilon)|A||B_{1}|$ and so
$e_{H_{1}}(A,B_{1})\geq(p-\varepsilon)|A||B_{1}|-(\gamma n+1)|B_{1}|$. Since

$(p-\varepsilon)|A|>(p-\varepsilon)(\frac{1}{4}\alpha n-1)>\gamma n+1,$

we get $e_{H_{1}}(A,B_{1})>0$, showing a contradiction.

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

###  2.2 Results on edges colorings

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

Let $x,y\in V(G)$. If $x$ and $y$ are contained in a same
$(\alpha,\beta)$-chain of $G$ with respect to $\varphi$, we say $x$ and $y$
are _$(\alpha,\beta)$ -linked_ with respect to $\varphi$. Otherwise, $x$ and
$y$ are _$(\alpha,\beta)$ -unlinked_ with respect to $\varphi$.

The fan argument was introduced by Vizing [20, 21] in his classical results on
the upper bounds of chromatic indices for simple graphs and multigraphs.
Multifans are generalized version of Vizing fans given by Stiebitz et al.
[18].

Let $G$ be a multigraph with maximum degree $\Delta$. For an edge $e=rs_{1}\in
E(G)$ and a coloring $\varphi\in\mathcal{C}^{\Delta}(G-e)$, a _multifan_
centered at $r$ w.r.t. $e$ and $\varphi$ is a sequence
$F=(r,rs_{1},s_{1},rs_{2},s_{2},\ldots,rs_{p},s_{p})$ with $p\geq 1$
consisting of distinct vertices $r,s_{1},s_{2},\ldots,s_{p}$ and edges
$rs_{1},rs_{2},\ldots,rs_{p}$ satisfying the following condition:

  1. (F1)

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

The set of vertices $r,s_{1},\ldots,s_{p}$ contained in $F$ is denoted by
$V(F)$. The following result regarding a multifan can be found in [18, Theorem
2.1], where an edge $e$ of $G$ is critical if
$\chi^{\prime}(G-e)<\chi^{\prime}(G)$.

######  Lemma 2.5.

Let $G$ be a multigraph with $\chi^{\prime}(G)=k\geq\Delta(G)+1$, $e=rs_{1}$
be a critical edge and $\varphi\in\mathcal{C}^{k}(G-e)$. If $F$ is a multifan
w.r.t. $e$ and $\varphi$, then $V(F)$ is $\varphi$-elementary.

In 1960’s, Vizing [22] and, independently, Gupta [8] proved the following
result, which can be proved by using the multifan arguments, where the
multiplicity $\mu(G)$ of a multigraph $G$ is $\max\\{e_{G}(u,v)\,:\,u,v\in
V(G)\\}$.

######  Theorem 2.6.

For every multigraph $G$ with multiplicity $\mu$,
$\chi^{\prime}(G)\leq\Delta(G)+\mu$.

Misra and Gries [14] described a polynomial time algorithm for coloring the
edges of any simple graph $G$ with at most $\Delta(G)+1$ colors.

Proved by König [12] that every bipartite multigraph has chromatic index as
its maximum degree.

######  Theorem 2.7.

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

######  Lemma 2.8.

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.

Proof. Assume to the contrary that $\chi^{\prime}(G)\geq\Delta(G)+2$. By
deleting edges and vertices from $G$ if necessary, we may assume that every
edge $e$ of $G$ is critical, i.e., $\chi^{\prime}(G-e)<\chi^{\prime}(G)$.
Assume first that there exists $u\in V(G)$ such that $u$ is not incident with
any multiple edges of $G$. Let $v\in N_{G}(u)$. Since $uv$ is critical,
$\chi^{\prime}(G-uv)\leq\chi^{\prime}(G)-1$. Let
$\varphi\in\mathcal{C}^{k}(G-uv)$ where $k\geq\Delta(G)+1$, and let $F$ be a
maximum multifan with respect to $uv$ and $\varphi$ and centered at $u$. Since
there are $k\geq\Delta(G)+1$ colors, for every $w\in V(G)$,
$\overline{\varphi}(w)\neq\emptyset$. By Lemma 2.5, if $w\in V(F)$, then every
color from $\overline{\varphi}(w)$ presents at $u$. Since $v\in V(F)$, we
conclude that $N_{G}[u]\subseteq V(F)$. By Lemma 2.5 again, $V(F)$ is
$\varphi$-elementary. Thus, $|\overline{\varphi}(V(F))|\geq
2+(k-d_{G}(u))+d_{G}(u)=k+2$, contradicting the fact that
$|\overline{\varphi}(V(F))|\leq k$.

Thus we assume that every vertex of $G$ is incident with some multiple edges.
Since $G$ is a star-multigraph, it has a vertex $x$ such that
$V(G)=N_{G}(x)\cup\\{x\\}$. Let $N_{G}(x)=\\{y_{1},\ldots,y_{t}\\}$, and let
$d_{i}=e_{G}(x,y_{i})$ for each $i\in[1,t]$. Since $G$ is a star-multigraph,
for each $y_{i}$, $x$ is the only vertex such that there are possibly multiple
edges between $y_{i}$ and $x$. Thus
$d_{G}(x)=\sum\limits_{i=1}^{t}d_{i}=\Delta(G)$ and $d(y_{i})\leq d_{i}+t-1$.
Let $H$ be the underlying simple graph of $G$. It is readily check that
$\Delta(H)\leq t$. By Theorem 2.6, $\chi^{\prime}(H)\leq t+1$. By assigning a
different color to each of the edges in $E(G)\setminus E(H)$, we see that
$\chi^{\prime}(G)\leq\chi^{\prime}(H)+\sum\limits_{i=1}^{t}(d_{i}-1)\leq\Delta(G)+1$.
This gives a contradiction to the assumption that
$\chi^{\prime}(G)\geq\Delta(G)+2$.

For the complexity of edge coloring $G$ using at most $\Delta(G)+1$ colors, we
analyze it below. The colors available will be $[1,\Delta(G)+1]$. Misra and
Gries [14] described a polynomial time algorithm for coloring the edges of any
simple graph $H$ with at most $(\Delta(H)+1)$ colors. Thus we first edge color
the underlying simple graph of $G[N_{G}(x)\cup\\{x\\}]$ using at most
$|N_{G}(x)|+1$ colors. This can be done in time of a polynomial in
$|N_{G}(x)|$. Then we color the other edges of $G[N_{G}(x)\cup\\{x\\}]$
greedily, which results in a coloring using at most $\Delta(G)+1$ colors by
the same argument as in the previous paragraph. It takes
$O(|N_{G}(x)|+\Delta(G))$ steps to edge color $G[N_{G}(x)\cup\\{x\\}]$ using
at most $\Delta(G)+1$ colors. If all edges of $G$ are already colored, then we
are done. Otherwise, we greedily color the other edges of $G$ until we
encounter an edge $uv_{1}$ such that $u$ and $v_{1}$ do not have a common
missing color with respect to the current edge coloring, say $\varphi$. We may
also assume that for any color $\alpha\in\overline{\varphi}(u)$ and any color
$\beta\in\overline{\varphi}(v_{1})$, $u$ and $v_{1}$ are
$(\alpha,\beta)$-linked. By symmetry, assume $u\not\in N_{G}(x)$. We construct
a multifan centered at $u$ with respect to $uv_{1}$ and $\varphi$. Assume
$F=(u,uv_{1},v_{1},uv_{2},v_{2},\ldots,uv_{s},v_{s})$ is a maximum multifan
centered at $u$. As shown in the first paragraph of this proof, the vertex set
of the multifan is not $\varphi$-elementary.

Assume fist that there exist $v_{i}$ with $i\in[2,s]$ and a color $\gamma$
such that $\gamma\in\overline{\varphi}(u)\cap\overline{\varphi}(v_{i})$. By
the construction of $F$, we may assume $v_{1},\ldots,v_{i}$ is the sequence
such that $\varphi(uv_{j})\in\overline{\varphi}(v_{j-1})$ for $j\in[2,i]$. We
color the edge $uv_{1}$ using the color on $uv_{2}$, recolor $uv_{j}$ using
the color on $uv_{j+1}$ for each $j\in[2,i-1]$, and recolor $uv_{i}$ by the
color $\gamma$. Thus assume there exist distinct $i,j\in[1,s]$ and a color
$\gamma$ such that
$\gamma\in\overline{\varphi}(v_{i})\cap\overline{\varphi}(v_{j})$. Let
$\alpha\in\overline{\varphi}(u)$. As at least one of $v_{i}$ and $v_{j}$ is
$(\alpha,\gamma)$-unlinked with $u$, say $v_{j}$, we do an
$(\alpha,\gamma)$-swap at $v_{j}$. (When both of $v_{i}$ and $v_{j}$ are
$(\alpha,\gamma)$-unlinked with $u$, we assume $j<i$). Then
$F^{*}=(u,uv_{1},v_{1},uv_{2},v_{2},\ldots,uv_{j},v_{j})$ is still a multifan
with respect to $uv_{1}$ and the current edge coloring, but $u$ and $v_{j}$
have a common missing color. We can then again color $uv_{1}$ as in the first
case. Thus we can color all the remaining edges of $G$ in this way using at
most $\Delta(G)+1$ colors. For each uncolored edge such as $uv_{1}$, it takes
$O(|V(G)|)$ steps to have it colored. As it takes $O(|N_{G}(x)|+\Delta(G))$
steps to edge color $G[N_{G}(x)\cup\\{x\\}]$, it then takes $O(|E(G)||V(G)|)$
steps to edge color $G$ using at most $\Delta(G)+1$ colors. ∎

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

######  Lemma 2.9 (Parity Lemma).

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

Let $G$ be a multigraph, $k\geq 0$ be an integer and
$\varphi\in\mathcal{C}^{k}(G)$. For a subset $X$ of $V(G)$ and a color
$i\in[1,k]$, define $\overline{\varphi}_{X}^{-1}(i)=\\{v\in
X:i\in\overline{\varphi}(v)\\}$, and $e(X)=|E(G[X])|$. 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 [13]
observed the following result.

######  Theorem 2.10.

Let $G$ be a graph 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.

We will need the following weaker version of “equalized” edge $k$-coloring.

######  Lemma 2.11.

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.

Proof. We first show that there exists an edge $k$-coloring $\varphi$ of $G$
such that $|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$
for each $i\in[1,k]$. Among all edge $k$-colorings of $G$, we choose $\varphi$
such that

$d_{\varphi}:=\sum\limits_{i=1}^{k}\left||\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(i)|\right|$

is minimum. If $d_{\varphi}=0$, then we are done. Thus $d_{\varphi}\geq 1$. By
the Parity Lemma, for each $i$,
$|\overline{\varphi}_{A}^{-1}(i)|+|\overline{\varphi}_{B}^{-1}(i)|\equiv
2n\pmod{2}$. Thus
$|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(i)|\equiv
2n\pmod{2}$. Since $d_{\varphi}>0$, we assume, by symmetry, that there exists
$i\in[1,k]$ such that
$|\overline{\varphi}_{A}^{-1}(i)|\equiv|\overline{\varphi}_{B}^{-1}(i)|\pmod{2}$
and $|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(i)|\geq 2$.
Since $e(A)=e(B)$, it follows that $\sum_{x\in A}d_{G}(x)=\sum_{y\in
B}d_{G}(y)$. This together with the fact that $|A|=|B|$, implies

$\operatorname{def}(A):=\sum\limits_{v\in A}(k-d_{G}(v))=\sum\limits_{v\in
B}(k-d_{G}(v))=:\operatorname{def}(B).$

On the other hand,

$\operatorname{def}(A)=\sum\limits_{i=1}^{k}|\overline{\varphi}_{A}^{-1}(i)|\quad\text{and}\quad\operatorname{def}(B)=\sum\limits_{i=1}^{k}|\overline{\varphi}_{B}^{-1}(i)|.$

Therefore
$\sum\limits_{i=1}^{k}|\overline{\varphi}_{A}^{-1}(i)|=\sum\limits_{i=1}^{k}|\overline{\varphi}_{B}^{-1}(i)|$.
Consequently, by the existence of $i\in[1,k]$ such that
$|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(i)|\geq 2$,
there exists $j\in[1,k]$ with $j\neq i$ such that
$|\overline{\varphi}_{B}^{-1}(j)|-|\overline{\varphi}_{A}^{-1}(j)|\geq 2$.
Next, we will do some Kempe changes on some $(i,j)$-chains to obtain another
edge $k$-coloring $\varphi^{\prime}$ so that
$d_{\varphi^{\prime}}<d_{\varphi}$, which will lead a contradiction to the
choice of $\varphi$.

If there exist distinct $u,v\in\overline{\varphi}_{A}^{-1}(i)$ such that $u$
and $v$ are $(i,j)$-linked with respect to $\varphi$, then we let
$\varphi^{\prime}=\varphi/P_{u}(i,j,\varphi)$. Clearly,
$d_{\varphi^{\prime}}=d_{\varphi}-4$, showing a contradiction to the choice of
$\varphi$. Thus for any two distinct $u,v\in\overline{\varphi}_{A}^{-1}(i)$,
$u$ and $v$ are $(i,j)$-unlinked with respect to $\varphi$. Similarly, for any
two distinct $u,v\in\overline{\varphi}_{B}^{-1}(j)$, $u$ and $v$ are
$(i,j)$-unlinked with respect to $\varphi$. Thus, for every
$u\in\overline{\varphi}_{A}^{-1}(i)$, the other end of $P_{u}(i,j,\varphi)$ is
in
$\overline{\varphi}_{A}^{-1}(j)\cup\overline{\varphi}_{B}^{-1}(i)\cup\overline{\varphi}_{B}^{-1}(j)$.
Similarly, for every $u\in\overline{\varphi}_{B}^{-1}(j)$, the other end of
$P_{u}(i,j,\varphi)$ is in
$\overline{\varphi}_{A}^{-1}(i)\cup\overline{\varphi}_{A}^{-1}(j)\cup\overline{\varphi}_{B}^{-1}(i)$.
Let $|\overline{\varphi}_{A}^{-1}(i)|=t_{A}$ and
$|\overline{\varphi}_{B}^{-1}(j)|=t_{B}$. Since
$|\overline{\varphi}_{A}^{-1}(j)|+|\overline{\varphi}_{B}^{-1}(i)|\leq
t_{B}-2+t_{A}-2$, there exists $u\in\overline{\varphi}_{A}^{-1}(i)$ and
$v\in\overline{\varphi}_{B}^{-1}(j)$ such that $u$ and $v$ are $(i,j)$-linked
with respect to $\varphi$. We let
$\varphi^{\prime}=\varphi/P_{u}(i,j,\varphi)$. Again
$d_{\varphi^{\prime}}=d_{\varphi}-4$, showing a contradiction to the choice of
$\varphi$.

Thus, we assume $G$ has an edge $k$-coloring $\varphi$ such that
$|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$ for every
$i\in[1,k]$, we call such $\varphi$ a _valid_ coloring. We choose a valid edge
$k$-coloring $\varphi$ such that
$g_{\varphi}:=\max_{i,j}\left||\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|\right|$
is smallest and subject to this, the number $h_{\varphi}$ of color pairs
$(i,j)$ such that
$\left||\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|\right|=g_{\varphi}$
is smallest. If $g_{\varphi}\leq 2$, then we are done. Thus $d_{\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)|\geq
3$. As $|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$ and
$|\overline{\varphi}_{A}^{-1}(j)|=|\overline{\varphi}_{B}^{-1}(j)|$, we know
$|\overline{\varphi}_{B}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(j)|\geq 3$. If
there exits $u\in\overline{\varphi}_{A}^{-1}(i)$ and
$v\in\overline{\varphi}_{B}^{-1}(i)$ such that
$P_{u}(i,j,\varphi)=P_{v}(x,j,\varphi)$, we let
$\psi=\varphi/P_{u}(i,j,\varphi)$. Clearly $\psi$ is still a valid coloring
with $g_{\psi}\leq g_{\varphi}$ and $h_{\psi}<h_{\varphi}$, showing a
contradiction to the choice of $\varphi$.

Thus for any $u\in\overline{\varphi}_{A}^{-1}(i)$ and any
$v\in\overline{\varphi}_{B}^{-1}(i)$, $P_{u}(i,j,\varphi)\neq
P_{v}(x,j,\varphi)$. As $E_{G}(A,B)=E_{G}(x,B)$ and different $(i,j)$-chains
are disjoint, there is at most one $u\in\overline{\varphi}_{A}^{-1}(i)$ and
$v\in\overline{\varphi}_{B}^{-1}(j)$ such that $u$ and $v$ are $(i,j)$-linked;
similarly, there is at most one $u\in\overline{\varphi}_{B}^{-1}(i)$ and
$v\in\overline{\varphi}_{A}^{-1}(j)$ such that $u$ and $v$ are $(i,j)$-linked.
As $|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|\geq 3$
and $|\overline{\varphi}_{B}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(j)|\geq 3$,
there exist distinct $u_{1},u_{2}\in\overline{\varphi}_{A}^{-1}(i)$ and
distinct $v_{1},v_{2}\in\overline{\varphi}_{B}^{-1}(i)$ such that
$P_{u_{1}}(i,j,\varphi)=P_{u_{2}}(x,j,\varphi)$ and
$P_{v_{1}}(i,j,\varphi)=P_{v_{2}}(x,j,\varphi)$. We now let
$\varphi^{\prime}=\varphi/P_{u_{1}}(i,j,\varphi)$. Note that
$P_{v_{1}}(i,j,\varphi^{\prime})=P_{v_{1}}(i,j,\varphi)$. We then let
$\psi=\varphi^{\prime}/P_{v_{1}}(i,j,\varphi^{\prime})$. Again $\psi$ is valid
with $g_{\psi}\leq g_{\varphi}$ and $h_{\psi}<h_{\varphi}$, showing a
contradiction to the choice of $\varphi$. Thus we have a valid coloring
$\varphi$ such that
$\left||\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{A}^{-1}(j)|\right|\leq
2$ for all $i,j\in[1,k]$.

In the first step, it takes $O(kn^{2})$ steps to find a valid edge coloring
$\varphi$, as for each $i\in[1,k]$, it takes $O(n)$-time to decrease
$|\overline{\varphi}_{A}^{-1}(i)|-|\overline{\varphi}_{B}^{-1}(i)|$ by 4; and
it take at most $n/2$ steps to eventfully have
$|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$. In the
second step, 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. ∎

##  3 Edge coloring regular lower-$(p,\varepsilon)$-regular star-multigraphs

The proofs in this section follow and extend ideas of Vaughan from [19]. We
will need the following version of Chernoff bound. (See e.g. [1, Theorem
A.1.16].)

######  Lemma 3.1.

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

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

######  Lemma 3.2.

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

  1. (i)

$|A|=|B|$;

  2. (ii)

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

  3. (iii)

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

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

Proof. Set $A$ and $B$ be two emptysets or “containers” for now. We first
partition $V(G)$ into $n$ pairs such that each pair $(x_{i},y_{i})$ is
partition into a same pair. We then assign one vertex of each pair to $A$ and
the other to $B$ uniformly at random. After the assignment, suppose the pairs
are $(a_{1},b_{1}),\ldots,(a_{n},b_{n})$ with $a_{i}\in A$ and $b_{i}\in B$.
Fix a vertex $v$, and define the random variables $X_{1},\ldots,X_{n}$ as
below:

$X_{i}=e_{G}(v,a_{i})-e_{G}(v,b_{i}).$

Clearly, $X_{i}\in\\{-1,0,1\\}$. So $|X_{i}|\leq 1$. If $a_{i},b_{i}\in N(v)$
or $a_{i},b_{i}\not\in N(v)$, then $\operatorname{Pr}(X_{i}=0)=1$. If
$|\\{a_{i},b_{i}\\}\cap N(v)|=1$, then
$\operatorname{Pr}(X_{i}=1)=\operatorname{Pr}(X_{i}=-1)=1/2$. Thus
$E(X_{i})=0$. Also it is easy to verify that for distinct $i,j\in[1,n]$,
$\operatorname{Pr}(X_{i}=x|Y_{j}=y)=\operatorname{Pr}(X_{i}=x)$ for all
$x,y\in\\{-1,0,1\\}$. Thus $X_{1},\ldots,X_{n}$ are mutually independent. Let
$S=X_{1}+\ldots+X_{n}$. Then $d_{A}(v)-d_{B}(v)=S$. By Lemma 3.1, for each
$v\in V(G)$,

$\displaystyle\operatorname{Pr}(|d_{A}(v)-d_{B}(v)|>n^{2/3}-1)$
$\displaystyle=$
$\displaystyle\operatorname{Pr}(|S|>n^{2/3}-1)\leq\operatorname{Pr}(|S|>0.9n^{2/3})$
$\displaystyle<$ $\displaystyle 2e^{-0.4n^{1/3}},$

where when $n\geq 32$, we have $n^{2/3}-1>0.9n^{2/3}$. There are $2n$
vertices, so the probability $p$ that there is a vertex $v$ for which the
inequality in condition (iii) does not hold is less than

$4ne^{-0.4n^{1/3}},$

which is less than $0.481$ when $n\geq 30000$. Thus for $n\geq n_{0}:=30000$,
there must be some partition of $V(G)$ into two equal parts $A$ and $B$
satisfying condition (ii) such that $|d_{A}(v)-d_{B}(v)|\leq n^{2/3}-1$ for
each $v\in V(G)$.

By a result of Srivastav and Stangier [17, Theorem 2.12], a partition that
satisfies condition (iii) with probability $\varepsilon$ for some
$\varepsilon>0$ can be constructed deterministically in $O(2n\times
n^{2}\log_{2}(\frac{2n\times n^{2}}{\varepsilon}))$-time, as desired. ∎

######  Theorem 3.3.

Let $0<1/n_{0}\ll\varepsilon\leq\eta\ll\alpha\leq p<1$, and let $G$ be a
regular lower-$(p,\varepsilon)$-regular star-multigraph on $2n\geq n_{0}$
vertices. Suppose $x$ is the multi-center, $2\leq|N_{G}(x)|\leq 2n-2$,
$e_{G}(x,v)\leq\eta n$ for every $v\in V(G)$, and $\delta(G)\geq 2\alpha n$.
Then $G$ is 1-factorizable or equivalently $\chi^{\prime}(G)=\Delta(G)$.
Furthermore, there is a polynomial time algorithm that finds an optimal
coloring.

Proof. Let $y\in V(G)\setminus N_{G}(x)$. We take
$2\lfloor\frac{|N_{G}(x)|}{2}\rfloor$ vertices from $N_{G}(x)$ and name them
as $\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}$, where
$t:=\lfloor\frac{|N_{G}(x)|}{2}\rfloor$. Applying Lemma 3.2 on $G-\\{x,y\\}$
and $\\{x_{1},y_{1},\ldots,x_{t},y_{t}\\}$, we obtain a partition
$\\{A^{\prime},B^{\prime}\\}$ of $V(G)\setminus\\{x,y\\}$ satisfying the
following properties:

  1. (i)

$|A^{\prime}|=|B^{\prime}|$;

  2. (ii)

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

  3. (iii)

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

Without loss of generality, we assume that $d_{B^{\prime}}(x)\geq
d_{A^{\prime}}(x)$. Then we let $A=A^{\prime}\cup\\{x\\}$ and
$B=B^{\prime}\cup\\{y\\}$. It is clear that $|A|=|B|$, $d_{B}(x)\geq
d_{A}(x)$, and $|d_{A}(v)-d_{B}(v)|\leq n^{2/3}+\eta n$ for all $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
$(d_{B}(x)-d_{A}(x))/2$ edges incident with $x$ from $E(H)$.

To prove the lemma, we will show that it is possible to find an edge coloring
of $G$ using $\Delta(G)$ colors, and we provide a procedure for constructing
such an edge coloring. Below gives an overview of the steps. At the start of
the process, $E(G)$ is assumed to be uncolored.

  1. Step 1

Find a “near equalized” edge-coloring of $G_{A,B}$ using $k$ colors, where
$k=\Delta(G_{A,B})+1$ as guaranteed by Lemma 2.8 and Lemma 2.11. Call
$\varphi$ the current edge coloring of $G_{A,B}$. By Lemma 2.11, we can
require $|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$;
furthermore, we require
$|\overline{\varphi}_{A}^{-1}(i)|,|\overline{\varphi}_{B}^{-1}(i)|\leq\eta^{\frac{1}{2}}n$
for each color $i\in[1,k]$.

  2. Step 2

Modify the partial edge-coloring of $G$ obtained in Step 1 by exchanging
alternating paths. When this step is completed, each of the $k$ color class
will be a 1-factor of $G$. During the process of this step, a few edges of
$H-E(G_{A,B})$ will be colored and a few edges of $G_{A}$ and $G_{B}$ will be
uncolored.

  3. Step 3

Let $R_{A}$ and $R_{B}$ be the subgraph of $G_{A}$ and $G_{B}$ that is induced
by the uncolored edges, respectively. We can ensure both $R_{A}$ and $R_{B}$
to be simple, i.e., not contain the vertex $x$. We find equalized edge-
colorings of $R_{A}$ and $R_{B}$ using exactly
$\ell:=\max\\{\Delta(R_{A}),\Delta(R_{B})\\}+1$ colors, which is possible by
Theorem 2.6 and Theorem 2.10. At the end of Step 3, all the edges in $G_{A}$
and $G_{B}$ will be colored, and so will a few edges of $H-E(G_{A,B})$. The
goal is to ensure that each of the $k+\ell$ color classes obtained so far is a
1-factor of $G$.

  4. Step 4

At the start of Step 4, all of the uncolored edges of $G$ belong to
$H-E(G_{A,B})$. Also, each color class is a 1-factor, so the subgraph of $G$
consisting of the uncolored edges is regular, of degree $\Delta(G)-k-\ell$.
This subgraph is bipartite, so we can color its edges using $\Delta(G)-k-\ell$
colors.

At the conclusion of Step 4, we obtain an edge coloring of $G$ using exactly
$\Delta(G)$ colors. We now give the details of each step. Let
$\mu(x)=\max\\{e_{G}(x,v)\,:\,v\in V(G)\\}$, which by the assumption is at
most $\eta n$.

Step 1

Let $k=\Delta(G_{A,B})+1$. Since $G$ is regular, $G_{A}$ and $G_{B}$ have the
same number of edges. Also by the construction of $G_{A,B}$,
$E_{G(A,B)}(A,B)=E_{G_{A,B}}(x,B)$. By Lemma 2.8 and Lemma 2.11, $G_{A,B}$ has
an edge $k$-coloring $\varphi$ 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$. The coloring $\varphi$ will be modified throughout the process and will
still be named as $\varphi$. Note that $k>\delta(G_{A,B})\geq\alpha
n-n^{2/3}-\mu(x)\geq\alpha n-n^{2/3}-\eta n>\frac{2}{3}\alpha n$. Since
$\Delta(G_{A,B})-\delta(G_{A,B})\leq n^{2/3}+\mu(x)\leq n^{2/3}+\eta n$,
$|\overline{\varphi}(v)|\leq\eta n+n^{2/3}+1$ for each $v\in A\cup B$. So the
average number of vertices in $A$ that a color misses is less than

$\frac{n(n^{2/3}+\eta n+1)}{k}\leq\frac{n(n^{2/3}+\eta n+1)}{\frac{2}{3}\alpha
n}<\frac{2\eta n}{\frac{2}{3}\alpha}<\eta^{1/2}n-2.$

As any two color classes differ in size by at most two, in this partial edge-
coloring of $G$, we have

$|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|<\eta^{1/2}n\quad\text{for
each $i\in[1,k]$}.$ (1)

Step 2

By interchanging alternating paths, we will increase the size of the $k$ color
classes obtained in Step 1 until each color class is a 1-factor of $G$. During
the procedure of Step 2, we will uncolor some of the edges of $G_{A}$ and
$G_{B}$, and will color some of the edges of $H-E(G_{A,B})$. Denote by $R_{A}$
and $R_{B}$ the subgraphs of $G_{A}$ and $G_{B}$ consisting of the uncolored
edges, which will initially be empty, but one or two edges will be added to
each of $R_{A}$ and $R_{B}$ when each time we exchange an alternating path. We
ensure that the following conditions are satisfied after the completion of
Step 2:

  1. (i)

$G_{A}$ and $G_{B}$ have the same number of uncolored edges, which is less
than $\eta^{\frac{1}{2}}n^{2}+\eta^{\frac{1}{2}}n$.

  2. (ii)

$\Delta(R_{A})$ and $\Delta(R_{B})$ are less than $\eta^{\frac{1}{4}}n+1$.

  3. (iii)

Each vertex of $G-x$ is incident with fewer than $2\eta^{\frac{1}{4}}n$
colored edges of $H$.

To ensure Condition (ii) is satisfied, we say that an edge $e=uv$ is _good_ if
$e\not\in E(R_{A})$ or $e\not\in E(R_{B})$ and
$d_{R_{A}}(u),d_{R_{A}}(v)<\eta^{\frac{1}{4}}n$ or
$d_{R_{B}}(u),d_{R_{B}}(v)<\eta^{\frac{1}{4}}n$. Thus a good edge can be added
to $R_{A}$ or $R_{B}$ without violating Condition (ii).

We will consider the $k$ colors in turn. For each $i\in[1,k]$, since
$|\overline{\varphi}_{A}^{-1}(i)|=|\overline{\varphi}_{B}^{-1}(i)|$, we can
pair up vertices in $\overline{\varphi}_{A}^{-1}(i)$ with vertices in
$\overline{\varphi}_{B}^{-1}(i)$, and will exchange exactly one alternating
path for each such pair. Suppose $(a,b)$ is one of the pairs, where $a\in A$,
$b\in B$, and $i\in\overline{\varphi}(a)\cap\overline{\varphi}(b)$. If
$x\not\in\\{a,b\\}$, we will exchange an alternating path $P$ from $a$ to $b$,
consisting of five edges with the first, third and fifth edges uncolored and
with the second and fourth edges good and colored $i$. (See Figure 1 (a).)
After $P$ is exchanged, $a$ and $b$ will be incident with edges of color $i$,
and one good edge will be added to each of $R_{A}$ and $R_{B}$. If
$x\in\\{a,b\\}$, we will exchange an alternating path $P$ from $a$ to $b$,
consisting of nine edges, where the first, third and fifth, seventh, and ninth
edges are uncolored and the second, fourth, sixth, and eighth edges are good
edges colored by $i$. (See Figure 1 (b).) After $P$ is exchanged, $a$ and $b$
will be incident with edges of color $i$, and two good edge will be added to
each of $R_{A}$ and $R_{B}$.

$a$$a_{1}$$a_{2}$$b$$b_{1}$$b_{2}$$x$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$b$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$A$$B$$A$$B$$(a)$$(b)$

-

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

Before demonstrating how such paths can be found, we show that Conditions (i),
(ii) and (iii) can be ensured at the end of Step 2. After the completion of
Step 1, each vertex is missed by fewer than $\eta^{\frac{1}{2}}n$ colors, for
each $i\in\overline{\varphi}(a)$ with $a\in A$ and $a\neq x$, exactly one edge
will be added to each of $R_{A}$ and $R_{B}$; when $x=a$, exactly two edges
will be added to each of $R_{A}$ and $R_{B}$. Thus there will always be fewer
than

$\eta^{\frac{1}{2}}n^{2}-\eta^{\frac{1}{2}}n+2\eta^{\frac{1}{2}}n=\eta^{\frac{1}{2}}n^{2}+\eta^{\frac{1}{2}}n$

edges in each of $R_{A}$ and $R_{B}$. Therefore Condition (i) will hold at the
end of Step 2. And as we only ever add good edges to $R_{A}$ and $R_{B}$,
Condition (ii) will hold automatically. We now show that Condition (iii) will
also be satisfied. Let $v\in V(G)\setminus\\{x\\}$ be any vertex. After Step
1, the only colored edges in $H$ are those incident with $x$, and so $v$ is
incident with at most $\eta n$ colored edges at the beginning of Step 2. In
the process of Step 2, the number of newly colored edges of $H$ that are
incident with $v$ will be equal to the number of alternating paths of length 5
or 9 containing $v$ that have been exchanged. The number of such alternating
paths of which $v$ is the first vertex will be equal to the number of colors
that missed $v$ at the end of Step 1, which is less than
$\eta^{\frac{1}{2}}n$. The number of alternating paths in which $v$ is not the
first vertex will be equal to the degree of $v$ in $R_{A}$, and so will be
less than $\eta^{\frac{1}{4}}n+1$. Hence the number of colored edges of $H$
that are incident with $v$ will be less than

$\eta n+\eta^{\frac{1}{2}}n+\eta^{\frac{1}{4}}n+1<2\eta^{\frac{1}{4}}n.$

This applies to all vertices in $G-x$, and so Condition (iii) will be
satisfied.

We now show the existence of such alternating paths. For a pair $(a,b)$ with
$a\in A$ and $b\in B$ such that
$i\in\overline{\varphi}(a)\cap\overline{\varphi}(b)$, in order to deal with
the two cases regarding whether $x=a$ using a uniform approach, we deal with
colors from $\overline{\varphi}(x)$ first. Note that
$|\overline{\varphi}(x)|\leq\eta^{\frac{1}{2}}n$ by (1). For each
$i\in\overline{\varphi}(x)$, we will add at most one edge to each of $R_{A}$
and $R_{B}$ to replace the pair $(x,b)$ by another pair that both miss the
color $i$. After we dealing with colors from $\overline{\varphi}(x)$, all the
edges of $R_{A}$ and $R_{B}$ are still good edges.

So we assume $a=x$ and let $i\in\overline{\varphi}(x)$. If there is a vertex
$y\in N_{B}(x)$ with $xy$ uncolored and $i\in\overline{\varphi}(y)$, we may
assume $y=b$ by repairing up vertices in $\overline{\varphi}_{A}^{-1}(i)$ with
vertices in $\overline{\varphi}_{B}^{-1}(i)$ if necessary. In this case, we
simply color $xy$ by the color $i$. Thus we assume that for every $y\in
N_{B}(x)$ with $xy$ uncolored, it holds that $i\not\in\overline{\varphi}(y)$.
Let $N_{B}$ be the set of vertices in $B$ that are joined with $x$ by an
uncolored edge and are incident with a good edge colored $i$. Since at most
$(d_{B}(x)-d_{A}(x))/2$ edges between $x$ and $B$ are assigned to $G_{A,B}$,
$x$ is incident to at least $\alpha n$ uncolored edges with the other
endvertex in $B$ at the end of Step 1. Furthermore, as
$|\overline{\varphi}(x)|\leq\eta^{\frac{1}{2}}n$, we know that in $H$, $x$ is
incident to at least $\alpha n-\eta^{\frac{1}{2}}n$ edges that are uncolored
during this procedure of dealing with colors from $\overline{\varphi}(x)$.
Since at this stage all the edges in $G_{B}$ colored $i$ are good edges,
$N_{B}\neq\emptyset$. We choose $b_{1}\in N_{B}$ and $b_{2}\in B$ such that
$\varphi(b_{1}b_{2})=i$. Note that such vertex $b_{2}$ exists since no edges
between $A$ and $B$ are colored by $i$: during this process, when a color is
used on an edge between $A$ and $B$, the color is already present at $x$.
Likewise, let $N_{A}$ 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$. Note that
$x\not\in N_{A}$ as the color $i$ is missing at $x$. By the same reasoning as
above, $N_{A}\neq\emptyset$. We choose $a_{1}\in N_{A}$ and $a_{2}\in A$ such
that $\varphi(a_{1}a_{2})=i$. Since the color $i$ was missing at $x$,
$a_{2}\neq x$. We now color $ab_{1}$ by $i$ and uncolor $b_{1}b_{2}$, color
$ba_{1}$ by $i$ and uncolor $a_{1}a_{2}$, and we pair up $a_{2}$ and $b_{2}$
as a pair that both miss the color $i$ to replace the original pair $(a,b)$.
We do this for every color from $\overline{\varphi}(x)$. After this step, all
the $k$ colors present at $x$, and each of $R_{A}$ and $R_{B}$ contains at
most $\eta^{\frac{1}{2}}n$ edges, and at most $2\eta^{\frac{1}{2}}n$ edges of
$H-E(G_{A,B})$ are colored.

Thus we assume $(a,b)$ is a pair with $a\neq x$. The same as before, let
$N_{B}$ 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$, and let $N_{A}$ be the set
of vertices in $A\setminus\\{x\\}$ that are joined with $b$ by an uncolored
edge and are incident with a good edge colored $i$ such that the edge is not
incident with $x$. Note that we exclude $x$ from $N_{A}$ to make $R_{A}$
simple. There are fewer than $\eta^{\frac{1}{2}}n^{2}+\eta^{\frac{1}{2}}n$
edges in $R_{B}$, so there are fewer than
$2(\eta^{\frac{1}{4}}n+\eta^{\frac{1}{4}})$ vertices of degree at least
$\eta^{\frac{1}{4}}n$ 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

$4(\eta^{\frac{1}{4}}n+\eta^{\frac{1}{4}})$ (2)

vertices in $B$ that are incident with a non-good edge colored $i$. In
addition, there are fewer than $\eta^{\frac{1}{2}}n$ vertices in $B$ that are
missed by the color $i$. So the number of vertices in $B$ that are not
incident with a good edge colored $i$ is less than

$4(\eta^{\frac{1}{4}}n+\eta^{\frac{1}{4}})+\eta^{\frac{1}{2}}n<4(\eta^{\frac{1}{4}}n+\eta^{\frac{1}{4}})+\eta^{\frac{1}{2}}n+2<5\eta^{\frac{1}{4}}n.$
(3)

By symmetry, the number of vertices in $A\setminus\\{x\\}$ that are not
incident with a good edge colored $i$ is less than $5\eta^{\frac{1}{4}}n-2$.

So for any vertex $v\in V(G)\setminus\\{x\\}$, the number of edges that join
$v$ with a vertex $w$ in the other part, where $w$ is incident with a good
edge colored $i$ and $x\not\in\\{v,w\\}$, is more than

$\alpha n-n^{2/3}-\eta n-5\eta^{\frac{1}{4}}n>\alpha
n-6\eta^{\frac{1}{4}}n>\frac{1}{2}\alpha n.$

Since $G-x$ is simple and $x\not\in\\{a,b\\}$, it follows that
$|N_{A}|>\frac{1}{2}\alpha n$ and $|N_{B}|>\frac{1}{2}\alpha n$. Let $M_{B}$
be the set of vertices in $B$ that are joined with a vertex in $N_{B}$ by an
edge of color $i$, and let $M_{A}$ be the set of vertices in $A$ that are
joined with a vertex in $N_{A}$ by an edge of color $i$. Note that $x\not\in
M_{A}$ by the choice of $N_{A}$. Note also that $|M_{B}|=|N_{B}|$ as each
vertex of $N_{B}$ is incident with an edge colored $i$, but some vertices may
be in both. Similarly $|M_{A}|=|N_{A}|$.

Since $|M_{A}|\geq\frac{1}{2}\alpha n>2\varepsilon n$ and
$|M_{B}|\geq\frac{1}{2}\alpha n>2\varepsilon n$ and $G$ is lower
$(p,\varepsilon)$-regular, it follows that
$e_{G}(M_{A},M_{B})\geq(p-\varepsilon)|M_{B}||M_{A}|$. By Condition (iii) of
this step, the number of colored edges in $H$ that are incident with a vertex
other than $x$ is at most $2\eta^{\frac{1}{4}}n$, we know that the number of
colored edges between $M_{A}$ and $M_{B}$ is at most
$2\eta^{\frac{1}{4}}n|M_{A}|<(p-\varepsilon)|M_{B}||M_{A}|$. Therefore, there
is an uncolored edge $a_{2}b_{2}\in E_{G}(M_{A},M_{B})$ with $a_{2}\in A$ and
$b_{2}\in B$. We now let $a_{1}\in N_{A}$ and $b_{1}\in N_{B}$ such that
$a_{1}a_{2}$ and $b_{1}b_{2}$ are colored by $i$. Then
$P=ab_{1}b_{2}a_{2}a_{1}b$ is a desired alternating path of five edges, where
the first, third and fifth edges are uncolored and the second and fourth edges
are good edges colored by $i$. We exchange $P$. After the exchange, the color
$i$ appears on edges incident with $a$ and $b$. By finding such paths for all
pairs of vertices $(a,b)$ that miss $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$.

Step 3

Each of the color classes for the colors from $[1,k]$ is now a 1-factor of
$G$. We now consider the graphs $R_{A}$ and $R_{B}$ that consist of the
uncolored edges of $G_{A}$ and $G_{B}$. Since the vertex $x$ was excluded from
$N_{A}$ and $M_{A}$ in Step 2, $x\not\in V(R_{A})$. Thus both $R_{A}$ and
$R_{B}$ are simple graphs. By Condition (i) of Step 2, $R_{A}$ and $R_{B}$
each has fewer than $\eta^{\frac{1}{2}}n^{2}+\eta^{\frac{1}{2}}n$ edges, and
$\Delta(R_{A}),\Delta(R_{B})<\eta^{\frac{1}{4}}n+1$. By Theorem 2.6 and
Theorem 2.10, $R_{A}$ and $R_{B}$ each has an equalized edge-coloring with
exactly $\ell:=\lfloor\eta^{\frac{1}{4}}n\rfloor+1$ colors
$k+1,\ldots,k+\ell$. Since $R_{A}$ and $R_{B}$ have the same number of edges,
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}$. There are fewer than
$\eta^{\frac{1}{2}}n^{2}+\eta^{\frac{1}{2}}n$ edges in each of $R_{A}$ and
$R_{B}$, and $\ell>\eta^{\frac{1}{4}}n$, so each of the color
$i\in[k+1,k+\ell]$ appears on fewer than
$\eta^{\frac{1}{4}}n+\eta^{\frac{1}{4}}+1<\eta^{\frac{1}{4}}n+2$ edges in each
of $R_{A}$ and $R_{B}$. We will now color some of the edges of $H$ with the
$\ell$ colors $[k+1,k+\ell]$ so that each of these color classes becomes a
1-factor of $G$. 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}|=|B_{i}|<2(\eta^{\frac{1}{4}}n+2)$

as $R_{A}$ and $R_{B}$ each contains fewer than $\eta^{\frac{1}{4}}n+2$ edges
colored $i$. Also $x\notin A_{i}$ as the vertex was excluded in $R_{A}$ in
Step 2. Let $H_{i}$ be the subgraph of $H$ obtained by deleting the vertex
sets $A_{i}$ and $B_{i}$ and removing all colored edges. Each vertex in $G-x$
is incident with fewer than

$2\eta^{\frac{1}{4}}n+\eta^{\frac{1}{4}}n+1<4\eta^{\frac{1}{4}}n$

edges of $H$ that are colored, since fewer than $2\eta^{\frac{1}{4}}n$ were
colored in Step 2 and at most $\eta^{\frac{1}{4}}n+1$ have been colored
already in Step 3. And each vertex in $G-x$ has fewer than
$2(\eta^{\frac{1}{4}}n+2)$ edges that join it with a vertex in $A_{i}$ or
$B_{i}$. So for $v\in V(H_{i})\setminus\\{x\\}$, $d_{H_{i}}(v)$ is more than

$\alpha n-n^{2/3}-\eta n-4\eta^{\frac{1}{4}}n-2(\eta^{\frac{1}{4}}n+2)>\alpha
n-7\eta^{\frac{1}{4}}n>\frac{1}{2}\alpha n.$

For the vertex $x$, recall that the missing colors at $x$ after Step 1 was
dealt with at the beginning of Step 2, and $x$ was not involved in the rest of
Step 2. Thus $d_{H_{i}}(x)$ is at least

$\displaystyle
d_{B}(x)-(d_{B}(x)-d_{A}(x))/2-\eta^{\frac{1}{2}}n-2(\eta^{\frac{1}{4}}n+2)$
$\displaystyle\geq$
$\displaystyle(d_{B}(x)+d_{A}(x))/2-\eta^{\frac{1}{2}}n-2(\eta^{\frac{1}{4}}n+2)$
$\displaystyle>$ $\displaystyle\alpha n-7\eta^{\frac{1}{4}}n>\frac{1}{2}\alpha
n.$

Therefore $\delta(H_{i})\geq\frac{1}{2}\alpha n$. Furthermore, by the analysis
above, each vertex of $H_{i}-x$ is incident with at most
$7\eta^{\frac{1}{4}}n$ edges from $E(G)\setminus E(H_{i})$. So $H_{i}$ has a
1-factor $F$ by Lemma 2.4. If we color the edges of $F$ with the color $i$,
then every vertex in $G$ is incident with an edge of color $i$, and so the
color class is now a 1-factor of $G$. We repeat this procedure for each of the
colors from $[k+1,k+\ell]$. After this has been done, each of these $\ell$
color classes is a 1-factor of $G$. 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, and each of the $k+\ell$ color classes is a 1-factor of $G$.

Step 4

Let $R$ be the subgraph of $G$ consisting of the remaining uncolored edges.
These edges all belong to $H$, so $R$ is a subgraph of $H$ and hence is
bipartite. As each of the $k+\ell$ color classes is a 1-factor of $G$, $R$ is
regular of degree $\Delta(R)=\Delta(G)-k-\ell$. Note that since $k\leq\alpha
n+n^{2/3}+\eta n$ and $\ell\leq\eta^{\frac{1}{4}}n+1$, $\Delta(R)\geq 2\alpha
n-k-\ell>(\alpha-2\eta^{\frac{1}{4}})n$. By Theorem 2.7 we can color the edges
of $R$ with $\Delta(R)$ colors from $[k+\ell+1,\Delta(G)]$. Clearly each of
these color classes is a 1-factor of $G$. This completes our edge coloring of
$G$ with $\Delta(G)$ colors. Each of the color classes is a 1-factor, so $G$
is 1-factorizable.

We check that there is a polynomial time algorithm to obtain a 1-factorization
of $G$. By Lemma 3.2, we can obtain a desired partition $\\{A,B\\}$ of $V(G)$
in polynomial time. Also, $G_{A,B}$ can be edge colored with the required
properties in polynomial time by Lemma 2.8. 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 pair of
vertices $(a,b)$ with a common missing color. 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 in the proof of Lemma 2.8, one
can obtain an equalized edge-coloring in polynomial time. The remaining
procedures are only about finding perfect matchings in bipartite graphs, which
can be done in polynomial time too such as applying the Hopcroft-Karp
algorithm [11]. Thus, there is a polynomial time algorithm that gives a
1-factorization of $G$. ∎

##  4 Proof of Theorem 1.3

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

######  Theorem 4.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 [9], the inductive proof yields a
polynomial time algorithm which finds an appropriate multigraph if it exists.

Let $G$ be a graph and $v\in V(G)$. Define
$\operatorname{def}_{G}(v)=\Delta(G)-d_{G}(v)$ to be the _deficiency_ of $v$
in $G$. It is clear that $G$ is overfull if and only if $|V(G)|$ is odd and
$\sum\limits_{v\in V(G)}\operatorname{def}_{G}(v)\leq\Delta(G)-2$. The proof
below follows the ideas of Glock, Kühn, and Osthus in the proof of Theorem 1.2
from [6].

######  Theorem 1.3.

For all $0<p<1$ there exist $\varepsilon,\eta>0$ such that for sufficiently
large $n$, the following holds: Suppose $G$ is a
lower-$(p,\varepsilon)$-regular graph on $n$ vertices and $n$ is odd.
Moreover, assume that $\Delta(G)-\delta(G)\leq\eta n$. Then
$\chi^{\prime}(G)=\Delta(G)$ if and only if $G$ is not overfull. Further,
there is a polynomial time algorithm which finds an optimal coloring.

Proof. Choose constants $\varepsilon,\eta$ and positive integer $n_{0}$ such
that $0<1/n_{0}\ll\varepsilon\leq\eta\ll p$. Let $G$ be a lower
$(p,\varepsilon)$-regular graph on $n\geq n_{0}$ vertices such that
$\Delta(G)-\delta(G)\leq\eta n$, where $n$ is odd. For any $X\subseteq V(G)$
with $|X|=\lceil\varepsilon n\rceil$, we have $E_{G}(X,V(G)\setminus
X)\geq(p-\varepsilon)(n-\varepsilon n-1)|X|$. Thus the average degree of a
vertex from $X$ is at least $(p-\varepsilon)(n-\varepsilon n-1)$, and do
$\delta(G)\geq(p-\varepsilon)(n-\varepsilon n-1)-\eta n>\frac{p}{2}n$. We let
$\alpha=p/2$ and use $\alpha n$ as a lower bound on $\delta(G)$ in the
following.

If $G$ is overfull, then $\chi^{\prime}(G)=\Delta(G)+1$. Thus assume $G$ is
not overfull. We will now add a new vertex to $G$ to form a multigraph with
even order. 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}$.

Since $G$ is not overfull and $n$ is odd, we have $2e(G)=\sum_{y\in
V(G)}d_{G}(y)\leq\Delta(G)(n-1)$. Consequently, $\sum_{y\in
V(G)}\operatorname{def}_{G}(y)\geq\Delta(G)$. Let
$V(G)=\\{x_{1},\ldots,x_{n}\\}$ and assume that $d_{G}(x_{1})\leq\ldots\leq
d_{G}(x_{n})$. Note that $d_{G}(x_{n})=\Delta(G)$. Assume $s\in[1,n-1]$ is the
smallest integer such that
$\sum\limits_{i=1}^{s}\operatorname{def}_{G}(x_{i})\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\limits_{i=1}^{s-1}\operatorname{def}_{G}(x_{i})$ edges between
$x$ and $x_{s}$, and call the resulting multigraph $G^{\prime}$. It is clear
that $G^{\prime}$ satisfies both of the constraints (i) and (ii). Since
$\Delta(G)-\delta(G)\leq\eta n$, we know that

$|N_{G^{\prime}}(x)|\geq\frac{\alpha}{\eta}\geq\frac{1}{\alpha^{3}}\geq 3.$

We claim that $G^{\prime}$ contains no $\Delta(G)$-overfull subgraph. 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 n-2$. If
$|X|<\varepsilon n+1$ or $|X|>n-\varepsilon n-1$, then $e_{G}(X,V(G)\setminus
X)\geq 2(\delta(G)-\varepsilon)n>\Delta(G)$. If $1+\varepsilon n\leq|X|\leq
n-\varepsilon n-1$, by the lower-$(p,\varepsilon)$-regularity of $G$, we have
$e_{G}(X,V(G)\setminus X)\geq
e_{G}(X\setminus\\{x\\},V(G)\setminus(X\cup\\{x)\\})\geq(p-\varepsilon)(|X|-1)(n-|X|-1)>\Delta(G)$.
Therefore $2e(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^{\prime}$ is obtained from $G^{\prime}$ by deleting a single vertex $y\in
V(G)$. Note that if $G^{\prime}-y$ is $\Delta(G)$-overfull for some $y\in
V(G^{\prime})$, then so is $G^{\prime}-x$ as $x$ has minimum degree in
$G^{\prime}$. However, $G^{\prime}-x=G$, which is not overfull by our
assumption. Thus $G^{\prime}-y$ is not $\Delta(G)$-overfull for any $y\in
V(G^{\prime})$.

Now $V(G^{\prime})=\\{x,x_{1},\ldots,x_{n}\\}$. Since $x$ has the smallest
degree in $G^{\prime}$ and $G=G^{\prime}-x$ is not overfull, $\sum_{i\geq
1}\operatorname{def}_{G^{\prime}}(x_{i})\geq\operatorname{def}_{G^{\prime}}(x)$.
Since $|V(G^{\prime})|=n+1$ is even,
$\operatorname{def}_{G^{\prime}}(x)+\sum_{i\geq
1}\operatorname{def}_{G^{\prime}}(x_{i})$ is even. Then by Theorem 4.1, there
exists a multigraph $H$ on $V(G)$ 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,n]$.
This multigraph $H$ will aid us to find a spanning regular subgraph of
$G^{\prime}$.

Note that
$\Delta(H)=\operatorname{def}_{G^{\prime}}(x)=\Delta(G)-\delta(G)\leq\eta n$
and $H$ contains isolated vertices. Thus
$\chi^{\prime}(H)\leq\Delta(H)+\mu(H)\leq 2\Delta(H)\leq 2\eta n<7\eta
n/\alpha$. Hence we can greedily partition $E(H)$ into $k\leq 7\eta n/\alpha$
matchings $M_{1},\ldots,M_{k}$ each of size at most $\alpha n/7$. Now we take
out linear forests from $G^{\prime}$ by applying Lemma 2.3 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 from $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 (each vertex of $G_{i-1}$ has degree 1 or
2 in $F_{i}$) in $G_{i-1}$ whose leaves are precisely the vertices in $M_{i}$.

Let $G_{0}=G^{\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 14\eta n/\alpha$, it
follows that $\delta(G_{i-1})\geq(\alpha-14\eta n/\alpha)\geq 6\alpha n/7$.
Moreover, let $\varepsilon^{\prime}=2\sqrt{14\eta/\alpha}$. Since $G^{\prime}$
is lower-$(p,2\varepsilon)$-regular by Proposition 2.1 (1) and
$\varepsilon^{\prime}>4\varepsilon$, $G_{i-1}$ is
lower-$(p,\varepsilon^{\prime})$-regular by Proposition 2.1 (2). Note that
$e_{G_{i-1}}(x,v)\leq e_{G^{\prime}}(x,v)\leq\eta n$ for every $v\in
V(G^{\prime})$ and $|N_{G_{i-1}}(x)|\geq\frac{6\alpha/7}{\eta}\gg 3$. Thus $x$
has in $G_{i-1}$ at least two neighbors outside the vertices of $M_{i}$.
Hence, since $M_{i}$ has size at most $\alpha n/7$, we can apply Lemma 2.3 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.$

Let $d=\Delta(G^{\prime})-2k$ and $\alpha^{\prime}=6\alpha/7$. We have shown
that $G_{k}$ is a $d$-regular, lower-$(p,\varepsilon^{\prime})$-regular star-
multigraph with $d\geq\alpha^{\prime}n$. Furthermore, $e_{G_{k}}(x,v)\leq\eta
n$ for every $v\in V(G_{k})$, $|N_{G_{k}}(x)|\geq\frac{6\alpha/7}{\eta}\gg 3$,
and $|N_{G_{k}}(x)|\leq n-1$ as $e_{G^{\prime}}(x,x_{n})=0$. By Theorem 3.3,
$\chi^{\prime}(G_{k})=d$. Now we color the edges of $F_{i}$ using 2 distinct
colors from $[d+1,d+2k]$ for each $i\in[1,k]$. It is clear that any edge
$d$-coloring of $G_{k}$ together with this coloring of
$\bigcup_{i=1}^{k}F_{i}$ gives an edge coloring of $G^{\prime}$ using
$d+2k=\Delta(G^{\prime})$ colors. As $G$ is a proper subgraph of $G^{\prime}$
with $\Delta(G)=\Delta(G^{\prime})$, it follows that
$\chi^{\prime}(G)=\Delta(G)$.

We lastly check that the procedure above yields a polynomial time algorithm.
Given $G$, we first check $\sum_{v\in V(G)}\operatorname{def}_{G}(v)$. If it
is at most $\Delta(G)-2$, then we conclude that
$\chi^{\prime}(G)=\Delta(G)+1$, and $G$ can be edge colored using
$\Delta(G)+1$ colors in polynomial time [14]. If $\sum_{v\in
V(G)}\operatorname{def}_{G}(v)>\Delta(G)-2$, then we add a new vertex $x$ to
$G$ and form $G^{\prime}$ as described in the beginning of this proof. Then we
can construct an edge $\Delta(G^{\prime})$-coloring of $G^{\prime}$ through
the process. Since Theorem 4.1, Lemma 2.3 and Theorem 3.3 give appropriate
running time statements, this can be achieved in time polynomial in $n$. ∎

## Acknowledgment

The author wishes to thank Drs. Daniela Kühn and Deryk Osthus for bringing up
the concept of derandomizing Chernoff bound, which helps to obtain a
polynomial time algorithm that gives an optimal edge coloring of the dense
quasirandom graphs of odd order.

## References

  * [1] N. Alon and J. H. Spencer.  The probabilistic method.  Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, third edition, 2008.  With an appendix on the life and work of Paul Erdős.
  * [2] A. G. Chetwynd and A. J. W. Hilton.  Star multigraphs with three vertices of maximum degree.  Math. Proc. Cambridge Philos. Soc., 100(2):303–317, 1986.
  * [3] A. G. Chetwynd and A. J. W. Hilton.  The edge-chromatic class of graphs with maximum degree at least $|V|-3$.  In Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), volume 41 of Ann. Discrete Math., pages 91–110. North-Holland, Amsterdam, 1989.
  * [4] 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.
  * [5] S. Fiorini and R. J. Wilson.  Edge-colourings of graphs, Research notes in Maths.  Pitman, London, 1977.
  * [6] S. Glock, D. Kühn, and D. Osthus.  Optimal path and cycle decompositions of dense quasirandom graphs.  J. Combin. Theory Ser. B, 118:88–108, 2016.
  * [7] S. Grünewald and E. Steffen.  Independent sets and 2-factors in edge-chromatic-critical graphs.  J. Graph Theory, 45(2):113–118, 2004.
  * [8] R. G. Gupta.  Studies in the Theory of Graphs.  PhD thesis, Tata Institute of Fundamental Research, Bombay, 1967.
  * [9] 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.
  * [10] I. Holyer.  The NP-completeness of edge-coloring.  SIAM J. Comput., 10(4):718–720, 1981.
  * [11] 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.
  * [12] D. König.  Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.  Math. Ann., 77(4):453–465, 1916.
  * [13] C. J. H. McDiarmid.  The solution of a timetabling problem.  J. Inst. Math. Appl., 9:23–34, 1972.
  * [14] J. Misra, and D. Gries.  A constructive proof of Vizing’s theorem.  Inform. Process. Lett., 41(3):131–133, 1992.
  * [15] M. Plantholt.  Overfull conjecture for graphs with high minimum degree.  J. Graph Theory, 47(2):73–80, 2004.
  * [16] P. D. Seymour.  On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.  Proc. London Math. Soc. (3), 38(3):423–460, 1979.
  * [17] A. Srivastav, and P. Stangier.  Algorithmic Chernoff-Hoeffding inequalities in integer programming.  Random Structures & Algorithms, 8(1):27–58, 1996.
  * [18] M. Stiebitz, D. Scheide, B. Toft, and L. M. Favrholdt.  Graph edge coloring.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2012.  Vizing’s theorem and Goldberg’s conjecture, With a preface by Stiebitz and Toft.
  * [19] E. R. Vaughan.  An asymptotic version of the multigraph 1-factorization conjecture.  J. Graph Theory, 72(1):19–29, 2013.
  * [20] V. G. Vizing.  On an estimate of the chromatic class of a $p$-graph.  Diskret. Analiz, (3):25–30, 1964.
  * [21] V. G. Vizing.  The chromatic class of a multigraph.  Kibernetika (Kiev), 1965(3):29–39, 1965.
  * [22] V. G. Vizing.  Critical graphs with given chromatic class.  Diskret. Analiz No., 5:9–17, 1965.