# Total coloring graphs with large maximum degree

Aseem Dalal111Indian Institute of Technology Delhi, Department of Mathematics,
Delhi India. Email<EMAIL_ADDRESS>Jessica McDonald222Auburn
University, Department of Mathematics and Statistics, Auburn U.S.A. Email:
<EMAIL_ADDRESS>Supported in part by Simons Foundation Grant #845698
Songling Shan333Auburn University, Department of Mathematics and Statistics,
Auburn U.S.A. Email<EMAIL_ADDRESS>Supported in part by NSF grant
DMS-2345869.

###### Abstract

We prove that for any graph $G$, the total chromatic number of $G$ is at most
$\Delta(G)+2\lceil\frac{|V(G)|}{\Delta(G)+1}\rceil$. This saves one color in
comparison with a result of Hind from 1992. In particular, our result says
that if $\Delta(G)\geq\frac{1}{2}|V(G)|$, then $G$ has a total colouring using
at most $\Delta(G)+4$ colors. When $G$ is regular and has a sufficient number
of vertices, we can actually save an additional two colors. Specifically, we
prove that for any $0<\varepsilon<1$, there exists $n_{0}\in\mathbb{N}$ such
that: if $G$ is an $r$-regular graph on $n\geq n_{0}$ vertices with
$r\geq\frac{1}{2}(1+\varepsilon)n$, then $\chi_{T}(G)\leq\Delta(G)+2$. This
confirms the Total Coloring Conjecture for such graphs $G$.

##  1 Introduction

In this paper, all graphs are simple unless otherwise explicitly stated. For
terms not defined here, we follow [22].

A _total coloring_ of a graph $G$ is an assignment of colors to the vertices
and edges of $G$ such that adjacent vertices receive different colors,
adjacent edges receive different colors, and if any edge $e$ is incident to
any vertex $v$, then $e,v$ also receive different colors. The _total chromatic
number_ of $G$, denoted $\chi_{T}(G)$, is the minimum number of colors needed
to totally color $G$. Since a vertex of maximum degree must receive different
colors from all its incident edges, every graph $G$ satisfies
$\chi_{T}(G)\geq\Delta(G)+1$. On the other hand, Behzad [1, Conjecture 1,
p.44], and independently Vizing [21], proposed the following conjecture.

######  Conjecture 1 (Total Coloring Conjecture).

Every graph $G$ has $\chi_{T}(G)\leq\Delta(G)+2$.

There has been extensive work towards the Total Coloring Conjecture; even the
planar case, which is not yet completely verified, has a significant
literature. An early survey of total coloring can be found in the 1995 book of
Jensen and Toft [14] (Section 4.9); see also the survey paper of Geethaa,
Narayananb, and Somasundaram [9] for a more modern account.

In this paper we focus on the Total Coloring Conjecture for graphs with large
maximum degree. For any graph $G$ with sufficiently large maximum degree,
Molloy and Reed [16] showed that $\chi_{T}(G)\leq\Delta(G)+10^{26}$. When the
maximum degree is large in comparison with $|V(G)|$, this can be improved. In
particular, Hind [13] proved that
$\chi_{T}(G)\leq\Delta(G)+2\lceil\frac{|V(G)|}{\Delta(G)}\rceil+1$ for any
graph $G$. Our first result in this paper is to improve Hind’s bound by (at
least) one.

######  Theorem 1.

Every graph $G$ satisfies
$\chi_{T}(G)\leq\Delta(G)+2\left\lceil\frac{|V(G)|}{\Delta(G)+1}\right\rceil$.

When $\Delta(G)\geq\frac{3}{4}|V(G)|$, Hilton and Hind [12] have already
confirmed Conjecture 1. However, for graphs with $\Delta(G)<\frac{3}{4}|V(G)$,
Theorem 1 offers an improved approximation to the Total Coloring Conjecture.
In particular, for all graphs with $\Delta(G)\geq\frac{1}{2}|V(G)|$, Theorem 1
says that $G$ has a total coloring using at most $\Delta(G)+4$ colors.

When the maximum degree of $G$ is large in comparison to $|V(G)|$ _and_ $G$ is
regular, more can be said. All $r$-regular graphs $G$ with
$r>\frac{2}{3}|V(G)|+\frac{23}{6}$ are known to satisfy the Total Coloring
Conjecture (Xie and He [24] and Xie and Yang [25]); this result is built on
earlier work by Chetwynd, Hilton and Zaho [4] and also Chew [5]. Our second
result in this paper is to show that for graphs on a sufficient number of
vertices, this fraction of $\tfrac{2}{3}$ can be lowered all the way to
$\tfrac{1}{2}$.

######  Theorem 2.

For any $0<\varepsilon<1$, there exists $n_{0}\in\mathbb{N}$ such that: if $G$
is an $r$-regular graph on $n\geq n_{0}$ vertices such that
$r\geq\frac{1}{2}(1+\varepsilon)n$, then $\chi_{T}(G)\leq\Delta(G)+2$.

The remainder of this paper is organized as follows. In Section 2, we use a
Vizing-fan type structure to prove two specific _edge-coloring_ results: one
for a hypergraph that is nearly a graph, and one for a graph that is nearly
bipartite. In Section 3 we use the hypergraph edge-colouring result, along
with a classic result of Hajnal and Szemeredi [11] on _equitable vertex-
colorings_ , to quickly prove Theorem 1. The nearly-biparitite edge-coloring
result is needed (along with the hypergraph edge-coloring result) for our
proof of Theorem 2. Section 4 contains some other needed preliminaries for
Theorem 2, divided into two subsections on matchings (in the complement of a
regular graph), and edge-colorings (which are somewhat equitable). At the
start of Section 5 we state one previous result by the third author, about a
vertex partition that will be essential for us, and then we present our proof
of Theorem 2.

##  2 Two edge-coloring results

A _hypergraph_ $H$ is a set of vertices $V(H)$ and a set of edges $E(H)$, each
of which is a subset of $V(H)$ of size at least two. In this paper we assume
that all hypergraphs are simple, meaning that any two edges intersect in at
most one vertex. A hypergraph $H$ is said to have rank $c$ if the largest set
in $E(H)$ has size $c$; if all edges in $H$ have size 2 then $H$ is a graph.
Given a hypergraph $H$, a vertex $v$ has _degree_ , denoted $d_{H}(v)$, equal
to the number of edges of $H$ it is a member of; $\Delta(H)$ denotes the
maximum degree of $H$. A _matching_ $M$ in a hypergraph $H$ is a set of edges,
none of which share any common vertices; a vertex is _saturated_ by $M$ if it
is contained in an edge of $M$; $V(M)$ denotes the set of all vertices in
$V(H)$ that are saturated by $M$, and; $M$ is _perfect_ if $V(H)=V(M)$. Given
an integer $k\geq 1$, a _$k$ -edge-coloring_ of a hypergraph $H$ (with at
least one edge) is an assignment of the colors $1,\ldots,k$ to the edges of
$H$ such that two edges sharing a common vertex must receive different colors.
For a vertex $x$ in a hypergraph $H$, by $\delta_{H}(x)$ we mean the set of
all edges containing $x$ in $H$; by $N_{H}(x)$ we mean the set of all vertices
in an edge with $x$ in $H$.

Given a hypgergraph $H$, a partial $k$-edge-coloring of $H$ is an edge-
coloring of some sub-hypergraph $H^{\prime}\subseteq H$. For $\varphi$ any
partial $k$-edge-coloring of $H$, and any vertex $v\in V(H)$, denote by
$\overline{\varphi}(v)$ the set of colors _missing_ at $v$, that is, the set
of all colors in $\\{1,2,\ldots,k\\}$ that are not used on an edge incident to
$v$ under $\varphi$. For a vertex set $X\subseteq V(H)$, define
$\overline{\varphi}(X)=\bigcup_{v\in X}\overline{\varphi}(v)$ to be the set of
missing colors of $X$. Given any pair of distinct colors
$\alpha,\gamma\in\\{1,\ldots,k\\}$, and given a vertex $v\in V(H)$ missing at
least one of $\alpha,\gamma$ under $\varphi$, we can consider the _maximal
$(\alpha,\gamma)$-chain $P$ beginning at $v$_, that is, the component
containing $v$ of the sub-hypergraph induced by edges colored $\alpha$ or
$\gamma$ under $\varphi$. The _end-vertices_ of such a chain are the vertices
that have degree one in the chain. If $H$ is a graph, then a maximal
$(\alpha,\gamma)$-chain is a maximal $(\alpha,\gamma)$-alternating path, and
its end-vertices are the endpoints of the path. Given such a maximal chain
$P$, note that by switching the colors $\alpha,\gamma$ on $P$ we get a new
partial $k$-edge-coloring $\varphi^{\prime}$ of $H$ where exactly the same set
of edges in $H$ have been colored; we denote this $\varphi^{\prime}$ by
$\varphi/P$.

Let $G$ be a graph and let $\varphi$ be a partial $k$-edge-coloring of $G$. A
_multifan_ centered at $r$ with respect to $\varphi$ is a sequence
$F_{\varphi}(r,s_{0}:s_{p})=(r,e_{0},s_{0},e_{1},s_{1},\ldots,e_{p},s_{p})$
with $p\geq 0$ consisting of distinct edges $e_{0},\ldots,e_{p}$ with
$e_{i}=rs_{i}$ for all $i$, where $e_{0}$ is left uncolored under $\varphi$,
and _for every edge $e_{i}$ with $i\in\\{1,\ldots,p\\}$, there exists
$j\in\\{0,\ldots,i-1\\}$ such that
$\varphi(e_{i})\in\overline{\varphi}(s_{j})$._

The above definition of a multifan first appeared in the book of Stiebitz et
al. [18] as a generalization of a _Vizing-fan_ , which Vizing used to prove
his eponymous theorem. Vizing required his fans to be simple, while multifans
are typically allowed to have parallel edges, although that difference is not
relevant for us here, since all graph (and hypergraphs) are simple in this
paper. The other difference in the structures is important for us here
however: in the italicized part of the definition above, Vizing required
$j=i-1$. We don’t require this, but we will however find it useful to consider
multifans which have this property. To this end, first note that if
$F_{\varphi}(r,s_{0}:s_{p})$ is a multifan, then for any integer
$p^{*}\in\\{0,\ldots,p\\}$, $F_{\varphi}(r,s_{0}:s_{p^{*}})$ is also a
multifan. A subsequence
$(s_{0}=s_{\ell_{0}},s_{\ell_{1}},s_{\ell_{2}},\ldots,s_{\ell_{t}})$ with the
property that
$\varphi(e_{\ell_{i}})=\alpha\in\overline{\varphi}(s_{\ell_{i-1}})$ for each
$i\in\\{1,\ldots,t\\}$, is called a _linear sequence_ of
$F_{\varphi}(r,s_{0}:s_{p})$. Given such a linear sequence, and given
$h\in\\{1,\ldots,t\\}$, we _shift from $s_{\ell_{h}}$ to $s_{0}$_ by
recoloring edge $e_{\ell_{i-1}}$ with $\varphi(e_{\ell_{i}})$ for all
$i\in\\{1,\ldots,h\\}$. Note that the result is a partial $k$-edge-coloring
where $e_{0}$ is colored and $e_{\ell_{h}}$ is not. These linear subsequences
and shifts have been implicitly used in many papers (see eg. [3]).

The first of the two edge-coloring results we will prove in this section is as
follows.

######  Lemma 3.

Let $H$ be a hypergraph with rank $c$ and suppose that there exists a matching
$M$ of $H$ such that all edges in $E(H)\setminus M$ have size two. Suppose
further that there exists a vertex $x\in V(H)$ with $N_{H}(x)\subseteq
V(H)\setminus V(M)$. If $|M|+|\delta_{H}(x)|\leq\Delta(H)+2c-1,$ then $H$ has
a $(\Delta(H)+2c-1)$-edge-coloring where every edge of $M\cup\delta_{H}(x)$
receives a different color.

Note that the $H$ in Lemma 3 is a hypergraph, but it is nearly a graph (all
but the matching edges are of size two). Our approach will be to find a
multifan within the edges of size two, and to consider linear subsequences and
shifts of this multifan, but also to use maximal $(\alpha,\gamma)$-chains in
the hypergraph which may indeed contain edges of larger sizes.

###### Proof.

_(Lemma 3)_ Let $\Delta=\Delta(H)$ and let $M^{*}=M\cup\delta_{H}(x)$. By
assumption,

$|M^{*}|=|M|+|\delta_{H}(x)|\leq\Delta+2c-1.$

Let $\varphi$ be a partial $(\Delta+2c-1)$-edge-coloring of $H$ with the
following properties:

  1. (P1)

every edge in $M^{*}$ receives a different color, and;

  2. (P2)

subject to (P1), $\varphi$ assigns colors to as many edges as possible.

If every edge in $H$ is colored by $\varphi$ then we are done, so we may
assume there is some edge $e_{0}$ that is uncolored by $\varphi$. Since
$e_{0}$ is uncolored it is not in $M^{*}$, so by assumption $e_{0}=uv$ for
some $u,v\in V(H)\setminus\\{x\\}$. Let $F$ be a multifan centered at $u$,
which is maximal subject to only containing edges of size two.

Since $u\neq x$, $u$ is incident with at most one edge from $M^{*}$. Since
$\varphi$ has $\Delta+2c-1$ colors (and $uv$ is uncolored), we also know that
$|\overline{\varphi}(v)|\geq 2c\geq 4$, and all of these colors must be
present at $u$ (otherwise $\varphi$ could be extended to $e_{0}=uv$). So there
are certainly linear sequences of $F$ containing no edge of $M^{*}$. We let
$F_{1}\subseteq F$ be a multifan induced by all the linear sequences of $F$
that don’t contain edges of $M^{*}$. Suppose
$F_{1}=(u,uw_{0},w_{0},uw_{1},w_{1},\ldots,uw_{t},w_{t})$, where $w_{0}=v$.

######  Claim 1.

Suppose $F_{2}\subseteq F_{1}$ corresponds to the union of any number of
linear sequences of $F$. Then
$\overline{\varphi}(u)\cap\overline{\varphi}(w_{i})=\emptyset$ for any
$w_{i}\in V(F_{2})$.

###### Proof of claim.

We already explained the truth of this for $w_{0}=v$, and can extend this
argument to the other $w_{i}$ as well. To this end, suppose that
$\overline{\varphi}(u)\cap\overline{\varphi}(w_{i})\neq\emptyset$ for some
$i$. Then there exists a linear sequence
$(u,w_{0},w_{i_{1}},\ldots,w_{i_{s}})$ of $F_{2}$ for which $w_{i_{s}}=w_{i}$.
Shift in $(u,w_{0},w_{i_{1}},\ldots,w_{i_{s}})$ from $w_{i_{s}}$ to $w_{0}$
and then color the edge $uw_{i}$ by a color in
$\overline{\varphi}(u)\cap\overline{\varphi}(w_{i})$. The resulting partial
$(\Delta+2c-1)$-edge-coloring $\varphi^{\prime}$ of $H$ still has every edge
in $M^{*}$ colored differently, since we excluded the edges of $M^{*}$ from
$F_{1}$ (and $F_{2}$). Hence $\varphi^{\prime}$ contradicts (P2). ∎

######  Claim 2.

For any color $\gamma\in\\{1,\ldots,\Delta+2c-1\\}$, there are at most $2c-1$
vertices from $\\{w_{0},\ldots,w_{t}\\}$ that are all missing $\gamma$ under
$\varphi$.

###### Proof of claim.

Suppose to the contrary that there exists such a $\gamma$, and let
$y_{1},y_{2},\ldots,y_{2c}$ be $2c$ distinct vertices of
$\\{w_{0},\ldots,w_{t}\\}$ all of which are missing $\gamma$ under $\varphi$.
Suppose, without loss of generality, that $y_{1}$ is the first vertex in the
order $w_{0},w_{1},\ldots,w_{t}$ for which
$\gamma\in\overline{\varphi}(y_{1})$. In particular, this implies that
$F_{1}(u,w_{0}:y_{1})$ does not contain any edge that is colored by $\gamma$.
Let $\alpha\in\overline{\varphi}(u)$; we know that $\alpha\neq\gamma$ by Claim
1. Consider the set $\mathcal{P}$ of maximal $(\alpha,\gamma)$-chains staring
at $u,y_{1},\ldots,y_{2c}$, respectively. At most one edge of $M^{*}$ is
colored by $\alpha$, and at most one edge of $M^{*}$ is colored by $\gamma$,
and any other edge coloured $\alpha$ or $\gamma$ has size two. So, if a chain
in $\mathcal{P}$ contains exactly one edge of $M^{*}$, then it has at most $c$
end-vertices; if it contains exactly two edges of $M^{*}$, then it can have at
most $2c$ end-vertices. Since there are at least $2c+1$ different end-vertices
for the chains in $\mathcal{P}$, this means that there is at least one chain
$P\in\mathcal{P}$ not containing any edges from $M^{*}$. In particular, all
edges in this chain will have size two. We let $\varphi^{\prime}=\varphi/P$
and consider two different cases according to whether or not $u$ is an
endpoint of $P$.

Case 1: _The vertex $u$ is an endpoint of $P$._

Suppose first that the other end of $P$ is $y_{1}$. Then in
$\varphi^{\prime}$, $u$ is missing $\gamma$, so in particular no
$\gamma$-edges appear in $F_{1}$ – if there were any before, they must have
been recolored to $\alpha$. However since these edge all occur after $y_{1}$
in the order of $F_{1}$, and $y_{1}$ is missing $\alpha$ in
$\varphi^{\prime}$, $F_{1}$ is still a multifan in $G$ under
$\varphi^{\prime}$. However now Claim 1 is not satisfied for
$\varphi^{\prime}$, leading to a contradiction in our choice of $\varphi$.

We may now assume that the other end of $P$ is not $y_{1}$. Here, at least
$F_{1}(u,w_{0}:y_{1})$ is a multifan with respect to $\varphi^{\prime}$
containing no edges of $M^{*}$. But now the color $\gamma$ is missing at both
$u$ and $y_{1}$ under $\varphi^{\prime}$, so Claim 1 is not satisfied for
$\varphi^{\prime}$, leading to a contradiction in our choice of $\varphi$.

Case 2: _The vertex $u$ is not an endpoint of $P$._

In this case we know that $P$ does not contain any edges of $F_{1}$.

First suppose that $y_{1}$ is not an end of $P$. Then $F_{1}$ is still a
multifan with respect to $\varphi^{\prime}$ containing no edges of $M^{*}$.
However then color $\alpha$ is missing at $u$ and at least one other vertex
from $\\{y_{2},y_{3},y_{4}\\}$ under $\varphi^{\prime}$. This means that Claim
1 is not satisfied for $\varphi^{\prime}$, leading to a contradiction in our
choice of $\varphi$.

We may now assume that $y_{1}$ is an end of $P$. Here, at least
$F_{1}(u,w_{0}:y_{1})$ is a multifan with respect to $\varphi^{\prime}$
containing no edges of $M^{*}$. But now the color $\alpha$ is missing at both
$u$ and $y_{1}$ under $\varphi^{\prime}$, so Claim 1 is not satisfied for
$\varphi^{\prime}$, leading to a contradiction in our choice of $\varphi$. ∎

Claims 1 and 2 tell us that

$|\overline{\varphi}(V(F_{1}))|\geq|\overline{\varphi}(u)|+\tfrac{1}{2c-1}\sum_{i=0}^{t}|\overline{\varphi}(w_{i})|.$
(1)

If we let $H^{\prime}$ be the hypergraph induced by all the colored edges in
$H$, then $|\overline{\varphi}(z)|\geq\Delta+2c-1-d_{H^{\prime}}(z)$ for all
$z\in V(H)$. Since $d_{H^{\prime}}(z)\leq\Delta$, we know that
$|\overline{\varphi}(z)|\geq 2c-1$ for any $z$. Since the edge $uw_{0}$ is
uncolored, we further know that $|\overline{\varphi}(w_{0})|\geq 2c$. So from
(1), we get

$|\overline{\varphi}(V(F_{1}))|\geq(\Delta+2c-1-d_{H^{\prime}}(u))+\tfrac{1}{2c-1}(2c)+\tfrac{1}{2c-1}((2c-1)t)>\Delta+2c+t-d_{H^{\prime}}(u).$
(2)

On the other hand, we know that there are exactly $t$ colored edges in
$F_{1}$, so there are exactly $d_{H^{\prime}}(u)-t$ coloured edges incident to
$u$ that are not included in $F_{1}$. At most one of these excluded colored
edges could be in $M^{*}$ (since $u\neq x$), while all the rest must have size
two (by assumption), and hence under $\varphi$ they must have a color not in
$\overline{\varphi}(\\{w_{0},\ldots,w_{t}\\})$, by (P2) and by definition of
$F_{1}$. Of course, by virtue of being incident to $u$, none of these excluded
colors are in $\overline{\varphi}(u)$ either. Hence we have found a set of at
least $d_{H^{\prime}}(u)-t-1$ colors from $\\{1,\ldots,\Delta+2c-1\\}$ that
are not in $\overline{\varphi}(V(F_{1})$. So

$|\overline{\varphi}(V(F_{1}))|\leq(\Delta+2c-1)-(d_{H^{\prime}}(u)-t-1)=\Delta+2c+t-d_{H^{\prime}}(u),$

contradicting (2). ∎

The second edge-coloring result that we prove in this section is as follows.
Note that while Lemma 3 is about a hypergraph that is almost a graph, the
following result is about a graph that is nearly a bipartite graph. Despite
the different settings, the arguments are very similar.

######  Lemma 4.

Let $G_{0}$ be a bipartite graph with bipartition $(A,B)$ and let $M$ be a
matching in $G_{0}$. Let $G$ be a graph obtained from $G_{0}$ by adding a new
vertex $x$ and adding some number of edges between $x$ and $V(G)\setminus
V(M)$. Let $k=\max\\{\Delta(G),k_{B}+1\\}$, where $k_{B}=\max\\{d_{G}(v):v\in
B\\}$. If $k\geq|M|+|\delta_{G}(x)|$, then $G$ has a $k$-edge-coloring where
every edge of $M\cup\delta_{G}(x)$ receives a different color.

###### Proof.

Let $\Delta=\Delta(G)$ and let $M^{*}=M\cup\delta_{G}(x)$. By assumption,
$|M^{*}|\leq k.$ Let $\varphi$ be a partial $k$-edge-colouring of $G$ with the
following properties:

  1. (P1)

every edge in $M^{*}$ receives a different color, and;

  2. (P2)

subject to (P1), $\varphi$ assigns colors to as many edges as possible.

If every edge in $G$ is colored by $\varphi$ then we are done, so we may
assume there is some edge $uv$ that is uncolored by $\varphi$. Note that
$u,v\neq x$, since otherwise $uv$ would be in $M^{*}$ and hence be colored
under $\varphi$. Suppose, without loss of generality, that $u\in A$, and let
$F$ be a maximal multifan centered at $u$.

We know that $v\in B$ (since $v\neq x$) so $k\geq d_{G}(v)+1$. We also know
that $uv$ is uncolored, therefore $|\overline{\varphi}(v)|\geq 2$. All of
these colors must be present at $u$ (otherwise $\varphi$ could be extended to
$e_{0}=uv$). On the other hand, since $u\neq x$, $u$ is incident with at most
one edge from $M^{*}$. So there are certainly linear sequences of $F$
containing no edge of $M^{*}$. We let $F_{1}\subseteq F$ be a multifan induced
by all the linear sequences of $F$ that don’t contain edges of $M^{*}$.
Suppose $F_{1}=(u,uw_{0},w_{0},uw_{1},w_{1},\ldots,uw_{t},w_{t})$, where
$w_{0}=v$. In particular, note that $x\neq w_{i}$ for any $i$, since its
incident edges are all in $M^{*}$.

######  Claim 3.

Suppose $F_{2}\subseteq F_{1}$ corresponds to the union of any number of
linear sequences of $F$. Then
$\overline{\varphi}(u)\cap\overline{\varphi}(w_{i})=\emptyset$ for any
$w_{i}\in V(F_{2})$.

###### Proof of claim.

This argument is identical to that of Claim 1 within the proof of Lemma 3. ∎

As $G_{0}=G-x$ is bipartite, for any distinct
$\alpha,\beta\in\\{1,\ldots,k\\}$ with
$\alpha\in\overline{\varphi}(u),\beta\in\overline{\varphi}(w_{i})$ for some
$i\in\\{0,\ldots,t\\}$, if there is an $(\alpha,\beta)$-alternating path
joining $u,w_{i}$, then it creates an odd cycle with $uw_{i}$, and hence we
know that the path must contain $x$ (as an internal vertex). Moreover, this
means that the path contains edges from $M^{*}$. Similarly, if
$\beta\in\overline{\varphi}(w_{i})\cap\overline{\varphi}(w_{j})$ for distinct
$i,j\in\\{1,\ldots,t\\}$, and there is an $(\alpha,\beta)$-alternating path
joining $w_{i}$ and $w_{j}$, then this creates an odd cycle with
$uw_{i},uw_{j}$, and hence we know that the path must contain $x$ (as an
internal vertex). Again, we also get that such a path contains edges from
$M^{*}$.

######  Claim 4.

For any $\gamma\in\\{1,\ldots,k\\}$, there is at most one vertex from
$\\{w_{0},\ldots,w_{t}\\}$ that is missing $\gamma$ under $\varphi$.

###### Proof of claim.

Suppose to the contrary that $y_{1},y_{2}$ are two distinct vertices of
$\\{w_{0},\ldots,w_{t}\\}$, both of which are missing $\gamma$ under
$\varphi$. Suppose, without loss of generality, that $y_{1}$ is the first
vertex in the order $w_{0},w_{1},\ldots,w_{t}$ for which
$\gamma\in\overline{\varphi}(y_{1})$. In particular, this implies that
$F_{1}(u,w_{0}:y_{1})$ does not contain any edge that is colored by $\gamma$.

Let $\alpha\in\overline{\varphi}(u)$; we know that $\alpha\neq\gamma$ by Claim
3. Consider the set of maximal $(\alpha,\gamma)$-alternating paths staring at
$u,y_{1},y_{2}$. If these three paths are all disjoint, then one of them, say
$P$, does not contain any edge of $M^{*}$ (since there are at most two edges
of $M^{*}$ with the colors $\alpha,\gamma$). On the other hand, suppose that
two of the three paths are in fact the same path $P^{*}$. By our discussion
prior to this claim, we know that $P^{*}$ must contain $x$ as an internal
vertex, and hence there are two $M^{*}$-edges colored $\alpha,\gamma$ on the
path $P^{*}$. But then again, among the three paths, we find one $P$ that does
not contain any edges of $M^{*}$.

We let $\varphi^{\prime}=\varphi/P$ and consider two different cases according
to whether or not $u$ is an endpoint of $P$. Note that in either case, we have
ensured that $P$ doesn’t contain any edges of $M^{*}$, does not contain $x$,
and only one of its endpoints is from $F_{1}$.

Case 1: _The vertex $u$ is an endpoint of $P$._

Since the other endpoint of $P$ is outside $F_{1}$, $F_{1}(u,w_{0}:y_{1})$ is
a multifan with respect to $\varphi^{\prime}$ containing no edges of $M^{*}$.
But now the color $\gamma$ is missing at both $u$ and $y_{1}$ under
$\varphi^{\prime}$, so Claim 3 is not satisfied for $\varphi^{\prime}$,
leading to a contradiction in our choice of $\varphi$.

Case 2: _The vertex $u$ is not an endpoint of $P$._ In this case we know that
$P$ does not contain any edges of $F_{1}$, and our proof is identical to case
2 of Claim 2 in Lemma 3. ∎

Claims 3 and 4 tell us that

$|\overline{\varphi}(V(F_{1}))|\geq|\overline{\varphi}(u)|+\sum_{i=0}^{t}|\overline{\varphi}(w_{i})|.$
(3)

If we let $G^{\prime}$ be the graph induced by all the colored edges in $G$,
then $\overline{\varphi}(z)\geq k-d_{G^{\prime}}(z)$ for all $z\in V(G)$. We
further argued that $|\overline{\varphi}(w_{0})|\geq 2$ earlier in this proof,
and the same argument (less being incident to an uncolored edge) tells us that
$|\overline{\varphi}(w_{i})|\geq 1$ for all other $i$. So from (3), we get

$|\overline{\varphi}(V(F_{1}))|\geq k-d_{G^{\prime}}(u)+2+t.$ (4)

On the other hand, we know that there are exactly $t$ colored edges in
$F_{1}$, so there are exactly $d_{G^{\prime}}(u)-t$ colored edges incident to
$u$ that are not included in $F_{1}$. At most one of these excluded colored
edges could be in $M^{*}$ (since $u\neq x$), while all the rest must have
colors that are not in $\overline{\varphi}(\\{w_{0},\ldots,w_{t}\\})$, by (P2)
and by definition of $F_{1}$. Of course, by virtue of being incident to $u$,
none of these excluded colors are in $\overline{\varphi}(u)$ either. Hence we
have found a set of at least $d_{G^{\prime}}(u)-t-1$ colors from
$\\{1,\ldots,k\\}$ that are not in $\overline{\varphi}(V(F_{1}))$. So we get

$|\overline{\varphi}(V(F_{1}))|\leq
k-(d_{G^{\prime}}(u)-t-1)<k-d_{G^{\prime}}(u)+2+t,$

contradicting (4). ∎

##  3 Proof of Theorem 1

A _$k$ -coloring_ of a graph $G$ is an assignment of the colors $1,2,\ldots,k$
to the vertices of $G$ such that adjacent vertices receive different colors.
Given a $k$-coloring $\varphi$, and given any $i\in\\{1,\ldots,k\\}$, we call
$V_{i}=\\{v\in V(G):\varphi(v)=i\\}$ the $i$th color class of $\varphi$; if
$|V_{i}|,|V_{j}|$ differ by at most one for any $i,j\in\\{1,\ldots,k\\}$, then
we say that $\varphi$ is _equitable_.

######  Theorem 5 (Hajnal and Szemerédi [11]).

Let $G$ be a graph and let $k\geq\Delta(G)+1$ be any integer. Then $G$ has an
equitable $k$-coloring.

We can now show that Theorem 1 follows quickly from Lemma 3 (and Theorem 5).

###### Proof of Theorem 1.

Let $G$ be a graph with $\Delta=\Delta(G)$. We will show that $G$ has a total
coloring using at most $\Delta+2\lceil\frac{|V(G)|}{\Delta+1}\rceil$ colors.

By Theorem 5, $G$ has an equitable ($\Delta$+1)-coloring, say $\varphi_{0}$.
Let $c=\lceil\frac{|V(G)|}{\Delta+1}\rceil$. By assumption, each color class
of $\varphi_{0}$ has size $c$ or $c-1$.

We construct a hypergraph $H$ as follows. We let $V(G)=V(H)\cup\\{x\\}$ for
one new vertex $x$. We start with $E(G)\subseteq E(H)$, and for any color
class $V_{i}$ of $\varphi_{0}$, if $|V_{i}|\geq 2$, we add $V_{i}$ as an edge
to $H$. If there is at least one color class of $\varphi_{0}$ that has size
one, then for each such color class $V_{j}$, we add $V_{j}\cup\\{x\\}$ as an
edge of size two to $H$.

Note that $d_{H}(w)=d_{G}(w)+1$ for all $w\in V(G)$, and
$d_{H}(x)\leq\Delta+1$ as $\varphi_{0}$ has exactly $\Delta+1$ distinct color
classes. Hence $\Delta(H)=\Delta+1$. We now apply Lemma 3 to $H$ with matching
$M=\\{V_{i}:\text{$V_{i}$ is a color class of $\varphi_{0}$ with size at least
2}\\}$ and vertex $x$. To see that this application is possible first note
that, $x$ has been defined as an isolate when $V(H)=V(M)$, and otherwise is in
an edge of size two with every vertex in $V(H)\setminus V(M)$. The quantity
$2c-1\geq 1$, since $c\geq 1$ (as $|V(G)|\geq\Delta+1$). Finally, the quantity
$|M|+|\delta_{H}(x)|$ is exactly the number of color classes of $\varphi_{0}$,
which is exactly $\Delta+1=\Delta(H)$. So from Lemma 3 we get a
($\Delta(H)+2c-1(=\Delta+2c)$)-edge-coloring $\varphi^{*}$ of $H$ such that
all the edges in $M\cup\delta_{H}(x)$ receive different colors.

Define $\varphi:V(G)\cup E(G)\rightarrow\\{1,\ldots,\Delta+2c\\}$ by:
$\varphi(e)=\varphi^{*}(e)$ for all $e\in E(G)$;
$\varphi(u)=\varphi^{*}(V_{i})$ for all $V_{i}\in M$ and $u\in V_{i}$, and;
$\varphi(w)=\varphi^{*}(xw)$ for all $w\in N_{H}(x)$. Note that this last
assignment ensures that every vertex in $G$ receives a color under $\varphi$,
since any vertex not in $V(M)$ is adjacent to $x$ in $H$. In $\varphi$,
adjacent edges receive different colors since this is true in $\varphi^{*}$.
Any vertex $w\in V(G)$ gets a different color from all its incident edges in
$\varphi$ since in $\varphi^{*}$, that color was used on an additional edge
incident to $w$. Finally, because every edge in $M\cup\delta_{H}(x)$ receives
a different color under $\varphi^{*}$, the only set of vertices receiving the
same colors under $\varphi$ are the vertices from the same color class (with
size at least two) of $\varphi_{0}$, which is an independent set in $G$. ∎

##  4 Additional Preliminaries

###  4.1 Matchings in the complement of a regular graph

The following result can be easily proved by applying Hall’s Marriage Theorem,
and one can also find a short proof in [20, Lemma 9].

######  Lemma 6.

Let $G[X,Y]$ be bipartite graph with $|X|=|Y|=n$. If $\delta(G)\geq n/2$, then
$G$ has a perfect matching.

Give a graph $G$ and a set $X\subseteq V(G)$, the _deficiency of $X$_ is
defined to be the quantity
$\operatorname{def}(G)=\operatorname{odd}(G-X)-|X|$, where for any graph $H$,
$\operatorname{odd}(H)$ is the number of odd components or components of odd
order of $H$. Note that any matching of $G$ must contain at least
$\operatorname{def}(X)$ unsaturated vertices, for any $X\subseteq V(G)$. The
deficiency of $G$ is
$\operatorname{def}(G)=\max\\{\operatorname{def}(X):X\subseteq V(G)\\}$. The
Tutte-Berge Formula [2, 19] asserts that the maximum size of a matching in $G$
is equal to $\tfrac{1}{2}(|V(G)|-\operatorname{def}(G))$. For any $X\subseteq
V(G)$, define an auxiliary bipartite multigraph $H(X)$ by contracting each
component in $G-X$ to a single vertex and deleting the edges of $G[X]$. As
part of his new proof of the Tutte-Berge Formula and the Gallai-Edmonds
Structure Theorem [6, 7, 8], West [23] defined $H(X)$ and proved (1)-(2) of
the following. Here, by a graph $G$ being _factor-critical_ , we mean that $G$
does not have a perfect matching, but $G-v$ does, for every $v\in V(G)$.

######  Lemma 7.

Let $G$ be a graph and let $X\subseteq V(G)$ be a maximal set with
$\operatorname{def}(X)=\operatorname{def}(G)$. Then

  1. (1)

_(West[23, Lemma 2])_ Every component of $G-X$ is factor-critical.

  2. (2)

_(West[23, Lemma 3])_ The bipartite multigraph $H(X)$ has a matching
saturating $X$.

  3. (3)

We may choose the matching $M$ in (2) so that if $d$ is the maximum degree in
$H$ over all vertices in $X$, then $M$ also saturates all vertices of
$V(H(X))\setminus X$ having degree at least $d$ in $H$.

To see Lemma 7(3), note first that any bipartite multigraph $H$ with
bipartition $(X,Y)$ where $d$ is the maximum degree in $H$ over all vertices
in $X$, has a matching saturating all vertices of degree at least $d$ in $Y$
(simply apply Hall’s Theorem to $(X,Y^{\prime})$, where $Y^{\prime}$ are those
vertices of $Y$ having degree at least $d$). Then note that given any two
matchings $M_{1},M_{2}$ of $H$ where $M_{1}$ saturates $X_{1}\subseteq X$ and
$M_{2}$ saturates $Y_{2}\subseteq Y$, there is a matching $M$ of $H$ that
saturates both $X_{1}$ and $Y_{2}$ (look at $M_{1}\cup M_{2}$ and delete an
appropriate set of edges).

We can now prove the following.

######  Lemma 8.

Let $G$ be an $n$-vertex $r$-regular graph for some integer $r\geq 0$. Then
$\overline{G}$ has a matching covering at least $n-\frac{n}{n-r}$ vertices of
$\overline{G}$.

Proof. Note that $\overline{G}$ is $(n-1-r)$-regular. If $\overline{G}$ has a
perfect matching, then we are done, so suppose not. Let $S\subseteq V(G)$ be a
maximal set with $\operatorname{def}(S)=\operatorname{def}(\overline{G})$, as
in Lemma 7. Then by this lemma, every component of $\overline{G}-S$ is factor-
critical.

Let $D$ of be an odd component of $\overline{G}-S$, and suppose that
$|V(D)|\leq n-r-1$. Then the number of edges between $D$ and $S$ in
$\overline{G}$ is at least

$|V(D)|(n-r-1-(|V(D)|-1)).$

The above function is concave down in $|V(D)|$, and given $1\leq|V(D)|\leq
n-r-1$, we get that the function is always at least $n-r-1$. Thus by Lemma
7(3), $\overline{G}$ has a matching saturating $S$ and all vertices from the
small components of $\overline{G}-S$ (i.e. those of size at most $n-r-1$). As
there are at most $\frac{n}{n-r}$ components of $\overline{G}-S$ with
$|V(D)|\geq n-r$, and because each of such component is factor-critical, it
follows that $\overline{G}$ has a matching that covers at least
$n-\frac{n}{n-r}$ vertices of $\overline{G}$. ∎

###  4.2 Equitable edge-colorings

We used equitable vertex-colorings in the proof of Theorem 1, and we shall use
an analog for edge-coloring for Theorem 2. The start of this is the following.

######  Theorem 9 (McDiarmid [15]).

Let $G$ be a graph with chromatic index $\chi^{\prime}(G)$. Then for all
$k\geq\chi^{\prime}(G)$, there is a $k$-edge-coloring of $G$ where every color
class contains either exactly $\lfloor|E(G)|/k\rfloor$ or exactly
$\lceil|E(G)|/k\rceil$ edges.

Given an edge coloring $\varphi$ of $G$ and a given a color $i$, we denote by
$\overline{\varphi}^{-1}(i)$ the set of all vertices in $G$ which are missing
color $i$ under $\varphi$. The following parity lemma will be helpful for us
(see eg. Lemma 2.1 in Grünewald and Steffen [10]).

######  Lemma 10.

Let $G$ be a graph and $\varphi$ be a $k$-edge-coloring of $G$ for some
integer $k\geq\Delta(G)$. Then
$|\overline{\varphi}^{-1}(i)|\equiv|V(G)|\pmod{2}$ for every color
$i\in\\{1,\ldots,k\\}$.

We now prove the following result about a sort of weakly-equitable of edge-
coloring.

######  Lemma 11.

Let $G$ be a graph and $F\subseteq E(G)$. Suppose that for some integer
$k\geq\Delta(G)$, $G$ has a $k$-edge-coloring such that all the edges in $F$
receive distinct colors. Then $G$ has a $k$-edge-coloring $\varphi$ such that
for any distinct $i,j\in\\{1,\ldots,k\\}$ it holds that

$\left||\overline{\varphi}^{-1}(i)|-|\overline{\varphi}^{-1}(j)|\right|\leq
5,$

and all edges in $F$ receive distinct colors.

Proof. We call a $k$-edge-coloring of $G$ _good_ if all the edges in $F$ are
assigned distinct colors. Among all good $k$-edge-colorings of $G$, we choose
$\varphi$ so that

$g_{\varphi}:=\max\\{\left||\overline{\varphi}^{-1}(i)|-|\overline{\varphi}^{-1}(j)|\right|:1\leq
i,j\leq k\\}$

is minimum. If $g_{\varphi}\leq 5$, then we are done, so suppose not. This
means there are colors $\alpha,\beta\in\\{1,\ldots,k\\}$ such that

$\left||\overline{\varphi}^{-1}(\alpha)|-|\overline{\varphi}^{-1}(\beta)|\right|=g_{\varphi}\geq
6.$ (5)

We may further assume that $\varphi$ has been chosen so as to minimize the
number of pairs $\alpha,\beta$ satisfying (5); let $h_{\varphi}$ be the number
of these pairs.

Without loss of generality, suppose that
$|\overline{\varphi}^{-1}(\alpha)|-|\overline{\varphi}^{-1}(\beta)|\geq 6$.
There are at most two edges from $F$ that are colored from
$\\{\alpha,\beta\\}$. Thus there are at most four vertices from
$\overline{\varphi}^{-1}(\alpha)$ that are endvertices of two
$(\alpha,\beta)$-alternating paths that each contain an edge of $F$. At most
$|\overline{\varphi}^{-1}(\beta)|$ vertices from
$\overline{\varphi}^{-1}(\alpha)$ are endvertices of
$|\overline{\varphi}^{-1}(\beta)|$ $(\alpha,\beta)$-alternating paths
involving a vertex from $\overline{\varphi}^{-1}(\beta)$. Thus there exist
distinct vertices $x,y\in\overline{\varphi}^{-1}(\alpha)$ occurring in one
common $(\alpha,\beta)$-alternating path that contains no edge of $F$. Let $P$
be the $(\alpha,\beta)$-alternating path with endpoints $x,y$, and let
$\psi=\varphi/P$. As $P$ does not contain any edges of $F$, the edges of $F$
are all still colored different colors under $\psi$, and hence $\psi$ is a
good $k$-edge-coloring of $G$. We claim that $g_{\psi}\leq g_{\varphi}$ and
$h_{\psi}<h_{\varphi}$, which yields a contradiction to our choice of
$\varphi$.

By our choice of $P$, we know that
$|\overline{\psi}^{-1}(\alpha)|=|\overline{\varphi}^{-1}(\alpha)|-2$ and
$|\overline{\psi}^{-1}(\beta)|=|\overline{\varphi}^{-1}(\beta)|+2$. Given (5)
and the definition of $g_{\varphi}$, for any other color
$\gamma\in\\{1,\ldots,k\\}\setminus\\{\alpha,\beta\\}$, we have

$|\overline{\varphi}^{-1}(\alpha)|\geq|\overline{\varphi}^{-1}(\gamma)|\geq|\overline{\varphi}^{-1}(\beta)|.$

But now, for any pair of colors $\\{\alpha^{\prime},\beta^{\prime}\\}$
satisfying (5), we have

$\displaystyle||\overline{\psi}^{-1}(\alpha^{\prime})|-|\overline{\psi}^{-1}(\beta^{\prime})||=$
$\displaystyle g_{\varphi}$ if
$\\{\alpha^{\prime},\beta^{\prime}\\}\cap\\{\alpha,\beta\\}=\emptyset$,
$\displaystyle||\overline{\psi}^{-1}(\alpha^{\prime})|-|\overline{\psi}^{-1}(\beta^{\prime})||=$
$\displaystyle g_{\varphi}-2$ if $\alpha^{\prime}=\alpha$ and
$\beta^{\prime}\neq\beta$,
$\displaystyle||\overline{\psi}^{-1}(\alpha^{\prime})|-|\overline{\psi}^{-1}(\beta^{\prime})||=$
$\displaystyle g_{\varphi}-2$ if $\alpha^{\prime}\neq\alpha$ and
$\beta^{\prime}=\beta$,
$\displaystyle||\overline{\psi}^{-1}(\alpha^{\prime})|-|\overline{\psi}^{-1}(\beta^{\prime})||=$
$\displaystyle g_{\varphi}-4$ if $\alpha^{\prime}=\alpha$ and
$\beta^{\prime}=\beta$.

Hence we have $g_{\psi}\leq g_{\varphi}$ and $h_{\psi}<h_{\varphi}$, a
contradiction to our choice of $\varphi$. ∎

##  5 Proof of Theorem 2

We will need the following result by the third author.

######  Lemma 12 (Shan [17, 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,\ldots,t\\}$;

  3. (iii)

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

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

We are now ready to present our proof of Theorem 2. We restate the theorem
here for convenience.

######  Theorem 2.

For any $0<\varepsilon<1$, there exists $n_{0}\in\mathbb{N}$ such that: if $G$
is an $r$-regular graph on $n\geq n_{0}$ vertices such that
$r\geq\frac{1}{2}(1+\varepsilon)n$, then $\chi_{T}(G)\leq\Delta(G)+2$.

###### Proof of Theorem 2.

Let $n_{0}$ be chosen to be at least the lower bound of $n$ in Lemma 12 and
such that $1/n_{0}\ll\varepsilon$. Let $G$ be an $r$-regular graph on $n\geq
n_{0}$ vertices with $r\geq\frac{1}{2}(1+\varepsilon)n$. By the result of
Hilton and Hind [12] that the Total Coloring Conjecture holds for graphs
$G^{\prime}$ with $\Delta(G^{\prime})\geq\frac{3}{4}|V(G^{\prime})|$, we may
assume that $r<\frac{3}{4}n$.

Lemma 8 tells us that $\overline{G}$ has a matching $M$ saturating at least
$n-\frac{n}{n-r}$ vertices. As $r<\frac{3}{4}n$, we get that $M$ leaves less
than $4$ vertices unsaturated. When $n$ is even, this means we can choose $M$
so that it saturates exactly $n-2$ vertices, and when $n$ is odd, we can
choose $M$ so that it saturates exactly $n-3$ vertices. When $n$ is odd, the
degree-sum formula additionally tells us that $r$ is even. In this case, we
may choose a matching $M^{*}\subseteq M$ saturating exactly $r-2$ vertices of
$G$.

We define $G^{*}$ to be a graph obtained from $G$ by adding the edges of $M$
to $G$, and by adding one new vertex $x$. If $n$ is even, we make $x$ a degree
two vertex whose neighbours are the two vertices of $V(G)\setminus V(M)$. When
$n$ is odd we make $x$ have degree $r+1$ by joining it to the three vertices
of $V(G)\setminus V(M)$ as well as the $r-2$ vertices of $V(M^{*})$. See
Figure 1 for a depiction of $G^{*}$.

Our general aim will be to define an $(r+2)$-edge-coloring of $G^{*}$ where
every edge of $M\cup\delta_{G^{*}}(x)$ receives a different color. If we can
do this (and we will indeed succeed when $n$ is even), then we get a total
coloring of $G$ with $r+2$ colors by giving each vertex $w\in V(G)$ the color
of the edge from $M\cup\delta_{G}(x)$ that is incident to $w$ in $G^{*}$. This
works, with these auxiliary edges acting as “placeholders” for the eventual
vertex-coloring, because the only vertices that get the same colour are
matched by $M$ (so they are non-adjacent in $G$).

Note that when $n$ is even,
$|M\cup\delta_{G^{*}}(x)|=\tfrac{n-2}{2}+2=\tfrac{n}{2}+1$ which is less than
$r+2$ by assumption. On the other hand, when $n$ is odd,
$|M\cup\delta_{G^{*}}(x)|=\tfrac{n-3}{2}+r-1$ which we expect to be strictly
larger than $r+2$. So, in the case when $n$ is odd, our stated aim is
hopeless, and we will need to adjust. These extra edges from $x$ will however
be important at the start of our edge-colouring process (detailed below in
five steps). Before the end of our process though, we will be able to safely
delete enough of the these edges so as to get our desired result.

Figure 1: The graph $G^{*}$ in the cases where $n$ is even and where $n$ is
odd. Note the edges of $M$ is bold in each graph, with $|M|=m-1$ in the even
case and $|M|=m-2$ in the odd case. Note also that in the odd case we have
$M^{*}\subseteq M$ of size $r-2$, whose endpoints are all joined to $x$.

Let $m\in\mathbb{Z}^{+}$ be such that $n=2m$ when $n$ is even and $n=2m-1$
when $n$ is odd. We define the following:

$\displaystyle Q$ $\displaystyle=$ $\displaystyle G^{*}-x\quad\text{if $n$ is
even},$ $\displaystyle Q$ $\displaystyle=$ $\displaystyle G^{*}\quad\text{if
$n$ is odd},$ $\displaystyle M$ $\displaystyle=$
$\displaystyle\\{x_{1}y_{1},\ldots,x_{m-1}y_{m-1}\\}\quad\text{if $n$ is
even},$ $\displaystyle M$ $\displaystyle=$
$\displaystyle\\{x_{1}y_{1},\ldots,x_{m-2}y_{m-2}\\}\quad\text{if $n$ is
odd},$ $\displaystyle V(Q)\setminus V(M)$ $\displaystyle=$
$\displaystyle\\{x_{m},y_{m}\\}\quad\text{if $n$ is even},$ $\displaystyle
V(Q)\setminus V(M)$ $\displaystyle=$
$\displaystyle\\{x_{m-1},y_{m-1},x_{m},y_{m}\\}\quad\text{if $n$ is odd, where
$x_{m-1}=x$}.$

Applying Lemma 12 on $Q$ and $N=\\{x_{1},y_{1},\ldots,x_{m},y_{m}\\}$, we
obtain a partition $(A,B)$ of $V(Q)$ satisfying the following properties:

  1. (P1)

$|A|=|B|$;

  2. (P2)

$|A\cap\\{x_{i},y_{i}\\}|=1$ for each $i\in\\{1,\ldots,m\\}$;

  3. (P3)

$\big{|}d_{A}(v)-d_{B}(v)\big{|}\leq m^{2/3}$ for each $v\in V(Q)$.

By renaming vertices if necessary, we assume that $x_{i}\in A$ and $y_{i}\in
B$ for each $i\in\\{1,\ldots,m\\}$, with
$M^{*}=\\{x_{1}y_{1},\ldots,x_{r-2}y_{r-2}\\}$. Let $Q_{A}=Q[A]$ and let
$Q_{B}=Q[B]$. See Figure 1.

Note that $d_{Q}(v)\in\\{r,r+1,r+2\\}$ for all $v\in V(G)$, since: if $v=x$ it
has degree $r+1$ in $Q$; if $v\in\\{x_{m},y_{m}\\}$ and $n$ is even then it
has degree $r$; if $v\in\\{y_{m-1},x_{m},y_{m}\\}$ and $n$ is odd then it has
degree $r+1$; if $v\in V(M^{*})$ and $n$ is odd then it has degree $r+2$, and;
otherwise $v$ has degree $r+1$. Note that for any vertex $v\in V(Q)$,
$d_{Q}(v)=d_{A}(v)+d_{B}(v)$, so by property (P3) this implies that

$d_{A}(v)=\tfrac{1}{2}\left((d_{A}(v)+d_{B}(v))+(d_{A}(v)-d_{B}(v))\right)\\\
\geq\tfrac{1}{2}(r-m^{2/3}).$

Analogous computations tell us that

$\displaystyle\delta(Q_{A}),\delta(Q_{B})$ $\displaystyle\geq$
$\displaystyle\tfrac{1}{2}\left(r-m^{2/3}\right),$ (6)
$\displaystyle\Delta(Q_{A}),\Delta(Q_{B})$ $\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left((r+2)+m^{2/3}\right).$ (7)

Note from our previous observations that $d_{Q}(x_{i})=d_{Q}(y_{i})$ for each
$i\in[1,m]$. So we have $\sum_{v\in A}d_{Q}(v)=\sum_{v\in B}d_{Q}(v)$, and
hence

$|E(Q_{A})|=|E(Q_{B})|.$ (8)

The remainder of our proof consists of five steps, through which we construct
our desired edge-coloring. Before we provide the details for each of these
steps, let us first give an outline, along with several necessary definitions.
In fact, we shall give two outlines: first an executive summary of the whole
process, and then a detailed outline of the five steps for edge-coloring.

Executive Summary of Edge-Coloring Procedure:

  * •

Let $k=\left\lceil\tfrac{1}{2}\left(r+2+m^{2/3}\right)\right\rceil+4$, and let
$\ell=\lceil m^{5/6}\rceil+1$.

  * •

In Steps 1-3 we will $k$-edge-color some edges in $Q$. In Steps 1-2 this will
primarily be those in $Q_{A},Q_{B}$, but then in Step 3 we will transform
these color classes to be as large as possible, i.e., so that each is a
perfect matching.

  * •

After Steps 1-3 we will not change any of the color classes $1,\ldots,k$, but
rather we will add new colors to deal with the remaining edges.

  * •

In Step 4 we will introduce $\ell$ new colors, and use them to color all the
remaining uncolored edges in $Q_{A},Q_{B}$. We will also extend these new
color classes to perfect matchings of $Q$ by coloring some additional edges of
$Q[A,B]$.

  * •

In Step 5 we color the remaining necessary edges of $Q$, and again we
introduce completely new colors to do so, getting us up to a total of $r+2$
colors. For $n$ even, every edge will be necessary and must be colored. When
$n$ is odd, we will finally describe how to delete some edges (between $x$ and
$B$ and some edges of $M^{*}$) that we do not need to color. This fifth and
last step is where we employ our Lemma 4.

Step 5 also includes some important details beyond what is written above:
because of course our goal is not to edge-color $Q$, but to totally color $G$.
In the $n$ even case, we will need to extend the coloring to the two edges
incident to $x$, which will then imply our desired total coloring (via the
argument given above). In the odd case we will need to describe why it is okay
that we didn’t color every edge of $Q$, and that it still leads to a total
coloring. As the reader will soon see however, it is the edge-coloring of $Q$
(or most of $Q$) that takes nearly all of the effort in this proof.

Detailed Outline of Edge-Coloring Procedure:

  * •

In Step 1 we will give a $k$-edge-coloring $\varphi_{0}$ to all edges of
$Q_{A}\cup Q_{B}$ plus a special set $M_{1}$ of $k$ edges; this whole colored
subgraph will be called $Q_{A,B}$. We will ensure that the edges of $M_{1}$
all get different colors.

  * •

When $n$ is even, we’ll choose $M_{1}=\\{x_{1}y_{1},\ldots,x_{k}y_{k}\\}$ in
Step 1.

  * •

When $n$ is odd, we’ll choose
$M_{1}=\\{x_{1}y_{1},\ldots,x_{k-1}y_{k-1},xx_{m}\\}$ in Step 1.

  * •

If $n$ is even we’ll let $\varphi_{0}=\varphi$ and go directly from Step 1 to
Step 3.

  * •

If $n$ is odd we’ll use Step 2 to transform $\varphi_{0}$ into $\varphi$. The
first thing we’ll do in Step 2 is say that we may assume $Q,M^{*}$ have a
special property with respect to $\varphi_{0}$ (involving the colors of
$\varphi_{0}(x)$), subject to uncoloring a small number (at most $m^{2/3}+5$)
edges of $Q_{A}$.

  * •

The second thing we’ll do in Step 2 ($n$ odd only) is to modify the $M_{1}$ we
chose in Step 1, and to change $\varphi_{0}$ to $\varphi$. In particular,
we’ll choose four special subsets $M_{x}^{1},M_{x}^{2},M_{x}^{3},M_{x}^{4}$ of
edges to remove from our initial $M_{1}$, and instead add to $M_{1}$ an equal
number of edges incident to $x$. The removed edges get uncolored (there will
be less than $6m^{2/3}+2\ell$ of them), and the new $M_{1}$-edges
corresponding to the removed edges from $M_{x}^{1}$ get colored (the other new
$M_{1}$-edges will already be colored). The new $M_{1}$ is a subset of
$M\cup\delta_{Q}(x)$, and we ensure it still has exactly $k$ edges, each of
which are colored a different color.

  * •

In Step 3 we will transform $\varphi$ so that each color class is a perfect
matching of $Q$. We will do this by pairing up vertices missing a common color
$i$ under $\varphi$, and then finding a path of edges between them which
alternates between uncolored and $i$-colored edges. We switch on each such
path to increase the size of our color class, as desired. We will ensure
however that the edges of $M\cup\\{xy_{m-1},xy_{m}\\}$ are not involved in
these paths. In particular, this means we’ll be maintaining our property that
all $k$ edges of $M_{1}$ are colored a different color (and the other edges of
$M$ are uncolored). In this step, some of the edges of $Q_{A}$ and $Q_{B}$
will be uncolored.

  * •

In Step 4 we leave the colors $1,2,\ldots,k$ alone, but extend $\varphi$ by
introducing $\ell$ new colors, say $k+1,\ldots,k+\ell$. We use these new
colors to quickly color the rest of the edges in $Q_{A},Q_{B}$ (by Vizing’s
Theorem), and then are able to extend these further to some edges of $Q[A,B]$
so that each color class is a perfect matching.

  * •

In Step 5, we define $R$ to be the remaining uncolored edges of $Q$ that we
will find necessary to color. When $n$ is even, this is every remaining
uncolored edge of $Q$. When $n$ is odd, we will omit from $R$ all the edges in
$M_{x}^{1}\cup M_{x}^{3}$ (selected in Step 2), as well as any uncolored edges
between $X$ and $V(M^{*})\cap B$. We then apply Lemma 4 to $R$ (or in the $n$
even case, to $R$ with $x$ and its two incident edges added back) to get our
desired edge-coloring. For both $n$ even and $n$ odd we will explain how this
implies our total coloring of $G$.

Let us now fill in all the details of the above outline.

Step 1: _Getting a $k$-edge-coloring $\varphi_{0}$ of $Q_{A,B}$._

We define $Q_{A,B}=(Q_{A}\cup Q_{B})+M_{1}$, where $M_{1}$ is defined as in
the above outline (depending on the partity of $n$). Note that in the case
where $n$ is odd,

$|M^{*}|=\tfrac{1}{2}(r-2)<k-1=|M_{1}\cap M|,$

so by renaming vertices if necessary, we may assume that $M^{*}\subseteq
M_{1}\cap M$.

We now apply Lemma 3 to get a $k$-edge-coloring of $Q_{A,B}$ where all the
edges of $M_{1}$ are colored differently. To see that this is possible, first
note that $Q_{A,B}$ is a hypergraph of rank $2$, and

$\Delta(Q_{A,B})+2(2)-1\leq\max\\{\Delta(Q_{A}),\Delta(Q_{B})\\}+1+3\leq k,$

where in the last inequality above we used (7). For the application of Lemma
3, we use the matching $M_{1}$, but for the vertex “$x$” in the lemma, we
simply add a dummy isolate vertex to the graph $Q_{A,B}$, which has no effect
on anything (other than vacuously meeting the existence condition in the
Lemma). Since $|M_{1}|=k$, the assumptions of Lemma 3 are satisfied, and we
get a $k$-edge-coloring edge coloring $\varphi_{0}$ of $Q_{A,B}$ where all the
edges of $M_{1}$ receive different colors.

Note that by our careful definition of $Q$, the quantity $|V(Q_{A,B})|$ is
always even. So coupling Lemma 10 and Lemma 11, we may choose our $k$-edge-
coloring $\varphi_{0}$ such that

$\left||\overline{\varphi}_{0}^{-1}(i)|-|\overline{\varphi}_{0}^{-1}(j)|\right|\leq
4$ (9)

for any $i,j\in\\{1,\ldots,k\\}$. By renaming some colors if necessary, we may
also assume that $\varphi_{0}(x_{i}y_{i})=i$ for all $i\in\\{1,\ldots,k\\}$.

For any vertex $v\in V(Q_{A,B})$,
$|\overline{\varphi}_{0}(v)|=k-d_{Q_{A,B}}(v)$. By substituting into this the
value of $k$ and the bound of $\delta(Q_{A,B})\leq\delta(Q_{A})$ obtained from
(6), we get that

$|\overline{\varphi}_{0}(v)|\leq m^{2/3}+5,$ (10)

for every $v\in V(Q_{A,B})$. Since $Q_{A,B}$ has exactly $2m$ vertices, this
means that the average number of vertices not seeing any particular colour is
at most

$\frac{2m(m^{2/3}+5)}{k}<4m^{2/3}-4.$

By (9), we get

$|\overline{\varphi}_{0}^{-1}(i)|<4m^{2/3}\quad\text{for each
$i\in\\{1,\ldots,k\\}$}.$ (11)

If $n$ is even we set $\varphi_{0}=\varphi$ and proceed to Step 3. If $n$ is
odd, we transform $\varphi_{0}$ to $\varphi$ according to Step 2.

Step 2: _Transforming $\varphi_{0}$ to $\varphi$ (and modifying $M_{1}$) when
$n$ is odd_.

We would like to say that for every color in $\overline{\varphi}_{0}(x)$, that
color is used on an edge of $M^{*}$. Since $|M_{1}|=k$ and since every edge of
$M_{1}$ is colored differently by $\varphi_{0}$, every color appears on an
edge of $M_{1}$. However, suppose that some color
$i\in\overline{\varphi}_{0}(x)$ is used on an edge in $M_{1}\setminus M^{*}$.
Since $|\overline{\varphi}_{0}(x)|\leq m^{2/3}+5$ (by (10)), and since
$|M^{*}|=\frac{1}{2}(r-2)$, there is some color $j\in\varphi_{0}(x)$ such that
$\varphi(x_{j}y_{j})=j$ and $x_{j}y_{j}\in M^{*}$. But then we can modify
$Q,M^{*},\varphi_{0}$ as follows:

  1. (F1)

delete the edges $xx_{j}$ and $xy_{j}$ from $Q$;

  2. (F2)

add the edges $xx_{i}$ and $xy_{i}$ to $Q$;

  3. (F3)

delete $x_{j}y_{j}$ from $M^{*}$, and;

  4. (F4)

add $x_{i}y_{i}$ to $M^{*}$.

  5. (F5)

color the edge $xx_{i}$ with the color $\varphi(xx_{j})$, and;

  6. (F6)

if there exists an edge of $Q_{A}$ that is incident with $x_{i}$ and is
colored by $\varphi_{0}(xx_{j})$, uncolor it.

Note that the above process will uncolor at most $m^{2/3}+5$ edges of $Q_{A}$.
We are okay with this sacrifice, so we may assume we have
$Q,M^{*},\varphi_{0}$ where every color from $\overline{\varphi}_{0}(x)$
appears on an edge of $M^{*}$.

The second half of this step concerns, as described in our outline, modifing
the $M_{1}$ we chose in Step 1, and changing $\varphi_{0}$ to a final coloring
we’ll call $\varphi$. We proceed as follows:

  1. (R1)

let $M_{x}^{1}\subseteq M^{*}$ be the set of edges on which the colors of
$\overline{\varphi}_{0}(x)$ appear;

  2. (R2)

uncolor all the edges in $M_{x}^{1}$, and;

  3. (R3)

color $xy_{i}$ by the color $i$.

Note that after the above process, all $k$ colors are present at $x$. We
continue as follows:

  1. (R4)

let $M_{x}^{2}\subseteq M_{1}$ be the set of edges on which the colors of
$\\{\varphi_{0}(xx_{j}):j\in\overline{\varphi}(x)\\}$ appear, and;

  2. (R5)

uncolor all the edges in $M_{x}^{2}$.

Note that $M_{x}^{1}\cap M_{x}^{2}=\emptyset$ since the former involves colors
missing at $x$ and the latter involves colors present at $x$.

The sets $M_{x}^{3}$ and $M_{x}^{4}$ are in a way analogous to
$M_{x}^{1},M_{x}^{2}$. For the first of these however, only the size really
matters. To this end, recall our definition of $\ell=\lceil m^{5/6}\rceil+1$.
We then proceed as follows:

  1. (R6)

let $M_{x}^{3}$ be a set of $\ell$ edges from $M^{*}\setminus(M_{x}^{1}\cup
M_{x}^{2})$;

  2. (R7)

let $M_{x}^{4}$ be the set of $\ell$ edges of $M_{1}$ that are colored by
colors from
$\\{\varphi_{0}(xx_{j}):\text{$x_{j}y_{j}\in M_{x}^{3}$ for some
$j\in\\{1,\ldots,k\\}$}\\}$, and ;

  3. (R8)

uncolor all the edges in $M_{x}^{3}\cup M_{x}^{4}$.

In order to see that step (6) is possible, note first that
$|M^{*}\setminus(M_{x}^{1}\cup M_{x}^{2})|\geq\tfrac{1}{2}(r-2)-2(m^{2/3}+5)$,
and then consider our assumption about the relative sizes of $r,n$, and the
fact that $n$ is sufficiently large.

We claim that we can choose $M_{x}^{3}$ and $M_{x}^{4}$ so that they are
disjoint. Let $e_{1}=x_{j}y_{j}$ be an arbitrary edge from
$M^{*}\setminus(M_{x}^{1}\cup M_{x}^{2})$ for some $j\in\\{1,\ldots,k\\}$.
Then clearly $\varphi_{0}(xx_{j})\neq\varphi_{0}(e_{1})$. We include $e_{1}$
in $M_{x}^{3}$, and include the edge of $M_{1}$ colored by
$\varphi_{0}(xx_{j})$ in $M_{x}^{4}$. Suppose for some
$t\in\\{1,\ldots,\ell\\}$, we have chosen $t$ edges for $M_{x}^{3}$ and
$M_{x}^{4}$, respectively, such that $M_{x}^{3}\cap M_{x}^{4}=\emptyset$. Then
there are at most $t$ non-chosen edges from $M^{*}\setminus(M_{x}^{1}\cup
M_{x}^{2})$ that are colored by colors from
$\\{\varphi_{0}(xx_{j}):\text{$x_{j}y_{j}$ is chosen for $M_{x}^{3}$}\\}$.
Also, there are at most $t$ unused edges from $x$ to
$V(M^{*}\setminus(M_{x}^{1}\cup M_{x}^{2}))\cap A$ in $Q$ that are colored by
colors from $\\{\varphi_{0}(x_{j}y_{j}):\text{$x_{j}y_{j}$ is chosen for
$M_{x}^{3}$}\\}$. Then

$|M^{*}\setminus(M_{x}^{1}\cup
M_{x}^{2})|-2t-2t>\tfrac{1}{2}(r-2)-2(m^{2/3}+5)-4\ell\geq 1,$

where again we use the assumption about the relative sizes of $r,n$, and the
fact that $n$ is sufficiently large. So we can find a non-chosen edge
$e_{t+1}=x_{i}y_{i}$, for some $i\in\\{1,\ldots,k\\}$, from
$M^{*}\setminus(M_{x}^{1}\cup M_{x}^{2})$ such that $\varphi_{0}(x_{i}y_{i})$
is distinct from all the colors on the edges joining $x$ and the vertices from
$A$ that are incident with an edge already chosen for $M_{x}^{3}$, and that
$\varphi_{0}(xx_{i})$ is distinct from all the colors on the chosen edges of
$M_{x}^{3}$. Now we can add $e_{t+1}$ to $M_{x}^{3}$ and add the edge of
$M_{1}$ that is colored by $\varphi_{0}(xx_{i})$ to $M_{x}^{4}$. By the choice
of the two new edges, we know that the updated sets $M_{x}^{3}$ and
$M_{x}^{4}$ are disjoint. Thus, repeating the above process, we can choose
$M_{x}^{3}$ and $M_{x}^{4}$ such that $M_{x}^{3}\cap M_{x}^{4}=\emptyset$.

Finally, with all of the above done, update $M_{1}$ to be
$M_{1}\setminus(M_{x}^{1}\cup M_{x}^{2}\cup M_{x}^{3}\cup M_{x}^{4})$ union
the set of edges that are incident with $x$ and are colored by a color that
was initially assigned to an edge from $M_{x}^{1}\cup M_{x}^{2}\cup
M_{x}^{3}\cup M_{x}^{4}$. This adjustment means that the set $M_{1}$ still
contains exactly one edge of each of the $k$ colors, but now these include
more edges of $\delta_{Q}(x)$. Note that the overall effect of the above
process was to color more of the edges in $\delta_{Q}(x)$, and uncolor at most
$|M_{1}^{x}\cup M_{2}^{x}\cup M_{x}^{3}\cup M_{x}^{4}|\leq 2(m^{2/3}+5)+2\ell$
edges.

Step 3: _Transforming the $k$ color classes from $\varphi$ into perfect
matchings._

During this step, by swapping along alternating paths, we will increase the
size of the $k$ color classes obtained in Step 1 until each color class is a
perfect matchings of $Q$. During this process, we will maintain the colors on
the edges of $M_{1}$ and we will maintiain the colors on the edges incident
with $x$ (when $n$ is odd). We will however, uncolor some of the edges of
$Q_{A}$ and $Q_{B}$. Let $R_{A},R_{B}$ be the the subgraphs induced by all
uncolored edges in $Q_{A},Q_{B}$, respectively. These graphs will both
initially be empty if $n$ is even, and $Q_{B}$ will also be initially empty
even if $n$ is odd. As we progress through this step however, one or two edges
will be added to each of $R_{A}$ and $R_{B}$ each time we swap colors on an
alternating path. We will tighlty control these uncolored edges, and will
ensure that the following conditions are satisfied after the completion of
Step 3:

  1. (C1)

$|E(R_{A})|=|E(R_{B})|<4m^{5/3}$.

  2. (C2)

$\Delta(R_{A}),\Delta(R_{B})<m^{5/6}$.

  3. (C3)

Each vertex of $Q$ is incident with fewer than $2m^{5/6}$ colored edges of
$Q[A,B]$, i.e., the bipartite subgraph of $Q$ induced by the bipartition
$(A,B)$.

At any point during our process, we say that an edge $e=uv$ is _good_ if
$e\not\in E(R_{A})\cup E(R_{B})$, the degree of $u$ and $v$ in both $R_{A}$
and $R_{B}$ is less than $m^{5/6}-1$, and in the case that $n$ is odd, $e$ is
not incident with any vertex from $V(M_{x}^{3})\cap B$. In particular, a good
edge can be added to $R_{A}$ or $R_{B}$ without violating condition (C2).

By Lemma 10, we know that $|\overline{\varphi}^{-1}(i)|$ is even for every
color $i\in\\{1,\ldots,k\\}$, so since $(A,B)$ is a partition of $V(Q)$, the
quantity $|\overline{\varphi}^{-1}_{A}(i)|-|\overline{\varphi}^{-1}_{B}(i)|$
is also even. We can pair up as many vertices as possible from
$\overline{\varphi}^{-1}_{A}(i),\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)$. We call each of these pairs a _missing-
common-color pair_ or _MCC-pair_ with respect to the color $i$. In fact, given
any MCC-pair $(a,b)$ with respect to some colour $i$, we will show that the
vertices $a,b$ are joined by some path $P$ (with at most 7 edges), where one
end of the path is an uncolored edge from $Q[A,B]$, and then the path
alternates between good edges (colored $i$) and uncolored edges. Given such a
path $P$, we will swap along $P$ by giving all the uncolored edges $i$, and
uncoloring all the colored edges. After this, both $a$ and $b$ will be
incident with edges colored $i$, and at most three good edges will be added to
$R_{A}\cup R_{B}$. Given the alternating nature of the path $P$, at most two
good edges will be added to any one of $R_{A},R_{B}$. The main difficulty in
this Step 3 (and perhaps in this proof) is to show that such path $P$ exists.
Before we do this, let us show that conditions (C1)-(C3) can be guaranteed at
the end of this swapping process, that is, at the end of Step 3. In fact, we
will only ever add good edges to and $R_{A}$ and $R_{B}$, so condition (C2)
will hold automatically. It remains then only to check (C1) and (C3).

Let us first consider condition (C1). We deleted at most $m^{2/3}+5$ edges of
$Q_{A}$ that were incident with $x$ after Step 1 but we have
$\overline{\varphi}_{0}(x)=\overline{\varphi}(x)$, and we uncolored at most
$m^{2/3}+5$ edges of $Q_{A}$ but for each of these edges, one of its
endvertices has the same set of missing colors under both $\varphi_{0}$ and
$\varphi$. So the sum of missing colors under $\varphi$ taken over all
vertices of $Q$ is at most $2m(m^{2/3}+5)+2(m^{2/3}+5)<3m^{5/3}$. Thus there
are less than $1.5m^{5/3}<2m^{5/3}$ MCC-pairs.

For each MCC-pair $(a,b)$ with $a,b\in V(Q)$, at most two 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 less than $4m^{5/3}$ uncolored edges in each
of $R_{A}$ and $R_{B}$. At the completion of Step 3, each of the $k$ color
classes is a perfect matching of $Q$ so each of $Q_{A}$ and $Q_{B}$ have the
same number of colored edges. Since $|E(Q_{A})|=|E(Q_{B})|$ by (8), we have
$|E(R_{A})|=|E(R_{B})|$. As $R_{B}$ is initially empty and less than
$4m^{5/3}$ edges will be added to $R_{B}$ by the end of Step 3, we have
$e(R_{B})<4m^{5/3}$. As $|E(R_{A})|=|E(R_{B})|$, we also have
$e(R_{A})<4m^{5/3}$. Thus Condition (C1) will be satisfied at the end of Step
3.

We now show that Condition (C3) will also be satisfied at the end of Step 3.
In the process of Step 3, the number of newly colored edges of $Q[A,B]$ that
are incident with a vertex $u\in V(Q)$ will equal the number of our chosen
alternating paths containing $u$. The number of such alternating paths of
which $u$ is the first vertex will equal the number of colors missing from $u$
at the end of Step 2. 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 $m^{5/6}$. As the edges in $M_{1}$ were colored in Steps 1-2, the
number of colored edges of $Q[A,B]$ that are incident with $u$ will be less
than $|\overline{\varphi}(u)|+m^{5/6}+1<2m^{5/6}$, where note that
$|\overline{\varphi}(u)|=k-|\varphi(u)|<3m^{2/3}$ as we uncolored at most
$k-\frac{1}{2}(r-m^{2/3})<m^{2/3}+4$ edges in $Q_{A}$ when we dealt with the
colors in $\overline{\varphi}_{0}(x)$ when $n=2m-1$, and all those edges could
be all incident with one single vertex in $Q_{A}$. Thus Condition (C3) will be
satisfied.

Let $i\in\\{1,\ldots,k\\}$. We will describe how to find the alternating paths
for the MCC-pairs with respect to $i$. There is one $i$-colored edge in
$M_{1}$, say $e_{i}$ with endpoints $V(e_{i})$, and we will be sure to avoid
it in all of the alternating paths joining our MCC-pairs. For each vertex in
an MCC-pair, we will see how to construct a short (two-edge) alternating path
from it that avoids $e_{i}$. We will see that there are so many choices for
such paths (even avoiding the vertex set $M_{x}^{3}$ as we will wish to do),
that we can connect them to link each MCC-pair.

Let $v\in V(Q)$. Suppose that $v\in S_{v}\in\\{A,B\\}$, and let $T_{v}$ be the
other one of $A,B$. Define $N_{1}(v)$ to be the set of all vertices in
$T_{v}\setminus(V(e_{i})\cup V(M_{x}^{3})\cup\\{x\\})$, where $V(e_{i})$ is
the set of the two endvertices of $e_{i}$, that are joined to $v$ by an
uncolored edge, and are incident to a good edge colored $i$. Let $N_{2}(v)$ be
the set of vertices in $T_{v}\setminus(V(e_{i})\cup V(M_{x}^{3})\cup\\{x\\})$
that are joined to a vertex of $N_{1}(v)$ by a good edge of color $i$. Note
that we have $|N_{1}(v)|=|N_{2}(v)|$, but some vertices may be in
$N_{1}(v)\cap N_{2}(v)$.

There are fewer than $4m^{5/3}$ edges in $R_{B}$ (by (C1)), so there are fewer
than $8m^{5/6}$ vertices of degree at least $m^{5/6}$ in $R_{B}$. Each non-
good edge is incident with one or two vertices of $R_{B}$ through the color
$i$. Thus the number of vertices in $B$ incident with a non-good edge colored
by $i$ is less than $16m^{5/6}$. In addition, by (11) there are fewer than
$3m^{2/3}$ vertices in $B$ that are missed by the color $i$. There are at most
$2|V(M_{x}^{3})\cap B|$ vertices of $B$ that are incident with an edge colored
by $i$ such that one endvertex of the edge is from $V(M_{x}^{3})\cap B$. So
the number of vertices in $B\setminus\\{y_{i}\\}$ that are incident with a
non-good edge colored $i$ is less than

$16m^{5/6}+3m^{2/3}+2\ell<19m^{5/6}.$ (12)

By symmetry, the number of vertices in $A\setminus\\{x_{i}\\}$ that are
incident with a non-good edge colored $i$ is less than $19m^{5/6}$. Therefore
for any $v\in V(Q)$, we have

$\displaystyle|N_{1}(v)|=|N_{2}(v)|$ $\displaystyle\geq$ $\displaystyle
d_{Q[A,B]}(v)-2-2m^{5/6}-19m^{5/6}-2$ (13) $\displaystyle\geq$
$\displaystyle\tfrac{1}{2}\left((1+\varepsilon)n-m^{2/3}\right)-22m^{5/6}$
$\displaystyle>$ $\displaystyle\tfrac{1}{2}(1+0.5\varepsilon)m,.$

where in the inequalities to get (13), the first term $-2$ is to make sure
that the endpoints of $e_{i}$ are not counted, the number $2m^{5/6}$ is the
maximum number of colored edges of $Q[A,B]$ that are incident with $v$ at the
end of Step 3 (as per (C3)), and the last term $-2$ is to make sure that when
$n$ is odd, the vertex $x$ and another vertex that is adjacent with $x$
through a good edge colored by $i$ is not counted.

Suppose now that we have some MCC-pair $(a,b)$ with respect to $i$, with $a\in
A$ and $b\in B$. By (13), we have
$|N_{2}(a)|,|N_{2}(b)|>\tfrac{1}{2}(1+0.5\varepsilon)m.$ We choose
$a_{1}a_{2}$ with color $i$ such that $a_{1}\in N_{1}(b)$ and $a_{2}\in
N_{2}(b)$. Now as $|N_{1}(a)|,|N_{1}(a_{2})|>\tfrac{1}{2}(1+0.5\varepsilon)m$
by (13), we know that $|N_{1}(a_{2})\cap N_{2}(a)|>\frac{1}{2}\varepsilon m$.
We choose $b_{2}\in N_{1}(a_{2})\cap N_{2}(a)$ so that
$b_{2}a_{2}\not\in(M\cup\\{xy_{m-1},xy_{m}\\})\setminus M_{1}$, and let
$b_{1}\in N_{1}(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
2(a)). 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}$.

$a$$a_{1}$$a_{2}$$b$$b_{1}$$b_{2}$$A$$B$$(a)$$a$$a_{2}$$a^{*}_{2}$$a^{*}$$b_{1}$$b_{2}$$b^{*}_{2}$$b^{*}_{1}$$A$$B$$(b)$
Figure 2: The alternating path $P$. Dashed lines indicate uncoloured edges,
and solid lines indicate edges with color $i$.

Consider then an MCC-pair $(a,a^{*})$ with respect to $i$ such that
$a,a^{*}\in A$ (the case for an MCC-pair $(b,b^{*})$ with $b,b^{*}\in B$ can
be handled similarly). By (13), we have
$|N_{2}(a^{*})|>\tfrac{1}{2}(1+0.5\varepsilon)m$. We take an edge
$b_{1}^{*}b_{2}^{*}$ colored by $i$ with $b_{1}^{*}\in N_{1}(a^{*})$ and
$b_{2}^{*}\in N_{2}(a^{*})$. Then again, by (13), we have
$|N_{2}(a)|,|N_{2}(b_{2}^{*})|>\tfrac{1}{2}(1+0.5\varepsilon)m.$ Therefore, as
each vertex $c\in N_{2}(b_{2}^{*})$ satisfies
$|N_{1}(c)|>\tfrac{1}{2}(1+0.5\varepsilon)m$, we have $|N_{1}(c)\cap
N_{2}(a)|>\tfrac{1}{2}\varepsilon m$. We take $a_{2}a_{2}^{*}$ colored by $i$
with $a_{2}^{*}\in N_{1}(b_{2}^{*})$ such that
$a_{2}^{*}b_{2}^{*}\not\in(M\cup\\{xy_{m-1},xy_{m}\\})\setminus M_{1}$ and
$a_{2}\in N_{2}(b_{2}^{*})$. Then we let $b_{2}\in N_{1}(a_{2})\cap N_{2}(a)$
such that $a_{2}b_{2}\not\in(M\cup\\{xy_{m-1},xy_{m}\\})\setminus M_{1}$, and
let $b_{1}$ be the vertex in $N_{1}(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 2(b)). 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}$. In this process, we added one edge to
$R_{A}$ and at most two edges to $R_{B}$.

We have shown above how to find alternating paths between all MCC-pairs, and
to modify $\varphi$ by switching on these. Each time we make such a switch, we
increase by one the size of the color class $i$ (and decrease by 2 the number
of vertices that are missing color $i$). By repeating this process, we can
therefore continue until the color class $i$ is a perfect matching of $Q$.
Durig this whole process, note that we did not alter any edge-colorings for
edges from $M_{1}$, nor any edges from $M\cup\\{xy_{m-1},xy_{m}\\}$. Hence we
still have that all edges in $M_{1}$ receive different colors and all edges in
$(M\cup\\{xy_{m-1},xy_{m}\\})\setminus M_{1}$ are uncolored.

Step 4: _Coloring $R_{A}$ and $R_{B}$ and extending the new color classes._

In this step we leave the colors $1,2,\ldots,k$ alone, but extend $\varphi$ by
introducing $\ell$ new colors, say $k+1,\ldots,k+\ell$. By (C2),
$\Delta(R_{A}),\Delta(R_{B})<m^{5/6}$. Recalling that $\ell=\lceil
m^{5/6}\rceil+1$, Vizing’s Theorem gives us an $\ell$-edge-coloring of
$R_{A}\cup R_{B}$ using the colors $k+1,\ldots,k+\ell$. By Theorem 9, we may
assume that all these new color classes differ in size by at most one. Since
$|E(R_{A})|=|E(R_{B})|$ by (C1), by possibly renaming some color classes we
may assume that each color appears on the same number of edges in $R_{A}$ as
it does in $R_{B}$.

By (C1) we get that $|E(R_{A})|,|E(R_{B})|<4m^{5/3}$, so since $\ell>m^{5/6}$,
each of the colors $k+1,\ldots,k+\ell$ appears on fewer than $4m^{5/6}+1$
edges in each of $R_{A}$ and $R_{B}$. We will now color some of the edges of
$G[A,B]-M$ with the $\ell$ new colors so that each class induces a perfect
matching. To this end, we perform the following procedure for each of the
$\ell$ colors in turn.

Let $i$ be a color in $\\{k+1,\ldots,k+\ell\\}$. We define $A_{i},B_{i}$ as
the sets of vertices in $A,B$, respectively, that are incident with edges
colored $i$. Then, from our discussion in the previous paragraph,
$|A_{i}|,|B_{i}|<2(4m^{5/6}+1)$. By our choices we in fact have
$|A_{i}|=|B_{i}|$; let $H_{i}$ be the subgraph of $Q[A,B]-M$ obtained by
deleting the vertex sets $A_{i}\cup B_{i}$ and removing all colored edges. We
will show that $H_{i}$ has a perfect matching and we will color these matching
edges with $i$.

By (C3), each vertex in $V(Q)$ is incident with fewer than $2m^{5/6}+\ell\leq
4m^{5/6}$ edges of $Q[A,B]$ that are colored. Also each vertex in $A$ has
fewer than $2(4m^{5/6}+1)$ edges to $B_{i}$ and each vertex in $B$ has fewer
than $2(4m^{5/6}+1)$ edges to $A_{i}$. So each vertex $v\in V(H_{i})$ (with
$v\neq x$ when $n$ is odd) is adjacent in $H_{i}$ to more than

$\tfrac{1}{2}\left((1+\varepsilon)m-m^{2/3}\right)-4m^{5/6}-2(4m^{5/6}+1)-2>\tfrac{1}{2}(1+0.5\varepsilon)m$

vertices, where the term $-2$ is due to the one or two edges in $M$ that are
possibly incident with $v$ in $Q$.

We are now ready to extend our color classes. If $n$ is even, then $H_{i}$ has
a perfect matching $F$ by Lemma 6; we color the edges of $F$ with the color
$i$ to get our desired result. So we may assume that $n$ is odd. Recall from
Step 2 that $|M_{x}^{3}|=\ell$ and we have $V(M_{x}^{3})\cap
V(R_{B})=\emptyset$. Also $x$ is not contained in $R_{A}$ by our construction
(see (13)). Thus all the edges in $E_{Q}(x,(V(M^{*})\setminus
V(M_{x}^{1}))\cap B)$ are uncolored in Step 2, and that
$\\{x\\}\cup(V(M_{x}^{3})\cap B)\subseteq V(H_{i})$. Thus, for each
$i\in\\{k+1,\ldots,k+\ell\\}$, we choose a distinct edge, say $xy$ from
$E_{Q}(x,V(M_{x}^{3})\cap B)$ and color it by $i$. Then $H_{i}-\\{x,y\\}$ has
a perfect matching $F$ by virtue of its minimum degree (as in the even case),
and we get our desired extension.

Step 5: _Coloring the remaining graph $R$ and getting a total coloring of
$G$._

As described in the outline, we define $R$ to be the remaining uncolored edges
of $Q$ that we will find necessary to color. When $n$ is even, this is every
remaining uncolored edge of $Q$. When $n$ is odd, we will omit from $R$ all
the edges in $M_{x}^{1}\cup M_{x}^{3}$ (selected in Step 2), as well as any
uncolored edges between $x$ and $V(M^{*})\cap B$.

Note that when $n$ is even, $\Delta(R)=r+1-k-\ell$. When $n$ is odd, we need
to make a few observations before being able to bound the maximum degree.
First, only vertices in $V(M^{*})\cap B$ have degree $r+2$ in $G^{*}$, with
all others having degree $r+1$ (since $n$ is odd). So it follows that for any
$w\in B$, we have $r-k-\ell\leq d_{R}(w)\leq r+1-k-\ell$; and for any $w\in
A$, we have $r-k-\ell\leq d_{R}(w)\leq r+2-k-\ell$. In any case, we have

$\Delta(R)\geq r-k-\ell\geq
r-\left(\left\lceil\tfrac{1}{2}\left(r+m^{2/3}\right)\right\rceil+4\right)-(\lceil
m^{5/6}\rceil+1)>\tfrac{1}{2}(1+0.5\varepsilon)m.$

In the case where $n$ is even, we let $R^{*}=R+\\{xx_{m},xy_{m}\\}$, that is
the remaining edges of $Q$ plus the last two edges of $G^{*}$ that are needed
to achieve our total coloring. If $n$ is odd, we just let $R^{*}=R$. We now
show that we can apply Lemma 4 to $R^{*}$.

Since all edges of $Q_{A},Q_{B}$ were colored in previous steps, $R^{*}$ is
indeed a bipartite graph, with a matching $M_{2}:=M\setminus M_{1}$), plus an
additional vertex $x$ with edges from $x$ to $V(G)\setminus V(M)$ when $n$ is
even, and from $x$ to $\\{y_{m-1},y_{m}\\}$ when $n$ is odd. As $|M|\leq m-1$
and $M_{1}$ and edges in $E_{Q}(x,V(M_{x}^{1}\cup M_{x}^{3}))$ covers
$2k-2|M_{x}^{2}|-2|M_{x}^{4}|$ vertices of $V(M)$, we get

$|M_{2}|\leq m-1-k+(m^{2/3}+5)+\ell<\frac{1}{2}m.$

When $n$ is even, we have $\Delta(R^{*})=r+1-k-\ell$. As $d_{R^{*}}(x)=2$, we
have $\Delta(R^{*})+1\geq|M_{2}|+|\delta_{R^{*}}(x)|$, and so the assumptions
of Lemma 4 is satisfied. So $R^{*}$ has a $(\Delta(R^{*})+1)$-edge-coloring
where all the edges of $M_{2}\cup\delta_{R^{*}}(x)$ are colored differently.

When $n$ is odd, we have $\Delta(R^{*})=r+2-k-\ell$. As all the edges in
$M_{x}^{1}\cup M_{x}^{2}\cup E_{Q}(x,\big{(}V(M^{*})\setminus(V(M_{x}^{1}\cup
M_{x}^{2}))\big{)}\cap B)$ were removed when we get $R^{*}$ from $R$, it
follows that $d_{R^{*}}(w)\leq r+1-k-\ell$ for every $w\in B$. As
$d_{R^{*}}(x)=2$, we have $\Delta(R^{*})\geq|M_{2}|+|\delta_{R^{*}}(x)|$, and
so the assumptions of Lemma 4 is satisfied. So $R^{*}$ has a
$\Delta(R^{*})$-edge-coloring where all the edges of
$M_{2}\cup\delta_{R^{*}}(x)$ are colored differently.

When $n$ is even, combining the color classes obtained above in $R^{*}$ with
the perfect matchings obtained in Steps 3 and 4, we have obtained an edge
coloring $\varphi^{*}$ of $G^{*}$ using $r+2$ colors such that all the edges
in $M\cup\delta_{G^{*}}(x)$ are colored differently. So, we get our desired
total coloring of $G$ using $(r+2)$ colors, as described early in our proof.

Now suppose that $n$ is odd. Combining the color classes in $R^{*}$ with the
perfect matchings obtained in Steps 3 and 4, we have obtained an edge coloring
of

$G^{**}:=G^{*}-M_{x}^{1}-M_{x}^{2}-E_{G^{*}}(x,(V(M^{*})\setminus(V(M_{x}^{1})\cup
V(M_{x}^{3})))\cap B).$

This edge coloring uses $r+2$ colors and all the edges in

$M^{**}:=(M\setminus(M_{x}^{1}\cup M_{x}^{3}))\cup
E_{G^{*}}(x,\\{x_{m-1},y_{m-1},y_{m}\\}\cup V(M_{x}^{1})\cup V(M_{x}^{3}))$

are colored differently. Note that $M^{**}$ covers all the vertices of $G$.
Define $\psi:V(G)\cup E(G)\rightarrow\\{1,2,\ldots,r+2\\}$ by:
$\psi(e)=\varphi^{*}(e)$ for all $e\in E(G)$; $\psi(u)=\varphi^{*}(e)$ for all
$e\in M^{**}$ such that $u\in V(G)$ and $u$ is incident with $e$ in $G^{*}$.
By the same argument as in the even case, $\psi$ is a total coloring of $G$
using at most $r+2$ colors. This completes the proof of Theorem 2. ∎

## References

  * [1] M. Behzad.  Graphs and Their Chromatic Numbers.  Ph.D. thesis, Michigan State University, East Lansing, 1965.
  * [2] C. Berge.  Sur le couplage maximum d’un graphe.  C. R. Acad. Sci. Paris, 247:258–259, 1958.
  * [3] Y. Cao, G. Chen, G. Jing, and S. Shan.  The core conjecture of Hilton and Zhao.  J. Combin. Theory Ser. B, 166:154–182, 2024.
  * [4] A. G. Chetwynd, A. J. W. Hilton, and C. Zhao.  The total chromatic number of graphs of high minimum degree.  J. London Math. Soc. (2), 44(2):193–202, 1991.
  * [5] K. H. Chew.  Total chromatic number of graphs of odd order and high degree.  Discrete Math., 205(1-3):39–46, 1999.
  * [6] J. Edmonds.  Paths, trees, and flowers.  Canadian J. Math., 17:449–467, 1965.
  * [7] T. Gallai.  Kritische Graphen. II.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 8:373–395, 1963\.
  * [8] T. Gallai.  Maximale Systeme unabhängiger Kanten.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:401–413, 1964\.
  * [9] J. Geetha, N. Narayanan, and K. Somasundaram.  Total colorings—a survey.  AKCE Int. J. Graphs Comb., 20(3):339–351, 2023.
  * [10] S. Grünewald and E. Steffen.  Independent sets and 2-factors in edge-chromatic-critical graphs.  J. Graph Theory, 45(2):113–118, 2004.
  * [11] A. Hajnal and E. Szemerédi.  Proof of a conjecture of P. Erdős.  In Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), volume 4 of Colloq. Math. Soc. János Bolyai, pages 601–623. North-Holland, Amsterdam-London, 1970.
  * [12] A. J. W. Hilton and H. R. Hind.  The total chromatic number of graphs having large maximum degree.  Discrete Math., 117(1-3):127–140, 1993.
  * [13] H. R. Hind.  An upper bound for the total chromatic number of dense graphs.  J. Graph Theory, 16(3):197–203, 1992.
  * [14] T. R. Jensen and B. Toft.  Graph coloring problems.  Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1995.  A Wiley-Interscience Publication.
  * [15] C. J. H. McDiarmid.  The solution of a timetabling problem.  J. Inst. Math. Appl., 9:23–34, 1972.
  * [16] M. Molloy and B. Reed.  A bound on the total chromatic number.  Combinatorica, 18(2):241–280, 1998.
  * [17] S. Shan.  Chromatic index of dense quasirandom graphs.  J. Combin. Theory Ser. B, 157:429–450, 2022.
  * [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] W. T. Tutte.  The factorization of linear graphs.  J. London Math. Soc., 22:107–111, 1947.
  * [20] E. R. Vaughan.  An asymptotic version of the multigraph 1-factorization conjecture.  J. Graph Theory, 72(1):19–29, 2013.
  * [21] V. G. Vizing.  Some unsolved problems in graph theory.  Russ. Math. Surv., 23:125–141, 1968.
  * [22] D. B. West.  Introduction to Graph Theory.  Prentice Hall, 2 edition, September 2000.
  * [23] D. B. West.  A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem.  European J. Combin., 32(5):674–676, 2011.
  * [24] D. Xie and Z. He.  The total chromatic number of regular graphs of even order and high degree.  Discrete Math., 300(1-3):196–212, 2005.
  * [25] D. Xie and W. Yang.  The total chromatic number of regular graphs of high degree.  Sci. China Ser. A, 52(8):1743–1759, 2009.