# Extending partial edge colorings of iterated cartesian products of cycles
and paths

Carl Johan Casselgren111Department of Mathematics, Linköping University,
SE-581 83 Linköping, Sweden. E-mail address<EMAIL_ADDRESS>Research supported by a grant from the Swedish Research council VR
(2017-05077).  Jonas B. Granholm222S:t Larsgatan 43A, SE-582 24 Linköping,
Sweden. E-mail address<EMAIL_ADDRESS>Fikre B.
Petros333Department of Mathematics, Addis Ababa University, 1176 Addis Ababa,
Ethiopia. E-mail address<EMAIL_ADDRESS>
(September 3, 2024)

Abstract. We consider the problem of extending partial edge colorings of
iterated cartesian products of even cycles and paths, focusing on the case
when the precolored edges satisfy either an Evans-type condition or is a
matching. In particular, we prove that if $G=C^{d}_{2k}$ is the $d$th power of
the cartesian product of the even cycle $C_{2k}$ with itself, and at most
$2d-1$ edges of $G$ are precolored, then there is a proper $2d$-edge coloring
of $G$ that agrees with the partial coloring. We show that the same conclusion
holds, without restrictions on the number of precolored edges, if any two
precolored edges are at distance at least $4$ from each other. For odd cycles
of length at least $5$, we prove that if $G=C^{d}_{2k+1}$ is the $d$th power
of the cartesian product of the odd cycle $C_{2k+1}$ with itself ($k\geq 2$),
and at most $2d$ edges of $G$ are precolored, then there is a proper
$(2d+1)$-edge coloring of $G$ that agrees with the partial coloring. Our
results generalize previous ones on precoloring extension of hypercubes
[Journal of Graph Theory 95 (2020) 410–444].

_Keywords: Precoloring extension; Edge coloring, Cartesian product; List
coloring_

##  1 Introduction

An (edge) precoloring (or partial edge coloring) of a graph $G$ is a proper
edge coloring of some subset $E^{\prime}\subseteq E(G)$; a $t$-edge
precoloring is such a coloring with $t$ colors. A $t$-precoloring $\varphi$ is
extendable if there is a proper $t$-edge coloring $f$ such that
$f(e)=\varphi(e)$ for any edge $e$ that is colored under $\varphi$; $f$ is
called an extension of $\varphi$. In general, the problem of extending a given
edge precoloring is an $\mathcal{NP}$-complete problem, already for
$3$-regular bipartite graphs [8, 11].

Edge precoloring extension problems seem to have been first considered in
connection with the problem of completing partial Latin squares and the well-
known Evans’ conjecture that every $n\times n$ partial Latin square with at
most $n-1$ non-empty cells is completable to a Latin square [10]. By a well-
known correspondence, the problem of completing a partial Latin square is
equivalent to asking if a partial edge coloring with $\Delta(G)$ colors of a
balanced complete bipartite graph $G$ is extendable to a $\Delta(G)$-edge
coloring, where $\Delta(G)$ as usual denotes the maximum degree. Evans’
conjecture was proved for large $n$ by Häggkvist [13], and in full generality
by Andersen and Hilton [1], and, independently, by Smetaniuk [16].

Another early reference on edge precoloring extension is [14], where the
authors study the problem from the viewpoint of polyhedral combinatorics. More
recently, the problem of extending a precoloring of a matching has been
considered in [9]. In particular, it is conjectured that for every graph $G$,
if $\varphi$ is an edge precoloring of a matching $M$ in $G$ using
$\Delta(G)+1$ colors, and any two edges in $M$ are at distance at least $2$
from each other, then $\varphi$ can be extended to a proper
$(\Delta(G)+1)$-edge coloring of $G$; here, by the distance between two edges
$e$ and $e^{\prime}$ we mean the number of edges in a shortest path between an
endpoint of $e$ and an endpoint of $e^{\prime}$; a distance-$t$ matching is a
matching where any two edges are at distance at least $t$ from each other. In
[9], it is proved that this conjecture holds for e.g. bipartite multigraphs
and subcubic multigraphs, and in [12] it is proved that a version of the
conjecture with the distance increased to 9 holds for general graphs.

Quite recently, with motivation from results on completing partial Latin
squares, questions on extending partial edge colorings of $d$-dimensional
hypercubes $Q_{d}$ were studied in [7]. Among other things, a characterization
of partial edge colorings with at most $d$ precolored edges that are
extendable to $d$-edge colorings of $Q_{d}$ is obtained, thereby establishing
an analogue for hypercubes of the characterization by Andersen and Hilton [1]
of $n\times n$ partial Latin squares with at most $n$ non-empty cells that are
completable to Latin squares. In particular, every partial $d$-edge coloring
with at most $d-1$ colored edges is extendable to a $d$-edge coloring of
$Q_{d}$. This line of investigation was continued in [5, 6] where similar
questions are investigated for trees.

In [4], similar questions are investigated for cartesian products of graphs.
Therein Evans-type edge precoloring extension results are obtained for the
cartesian products of complete and complete bipartite graphs with $K_{2}$,
respectively, as well as for the product of $K_{2}$ with graphs of small
maximum degree and trees. Moreover, similar results for the cartesian product
of $K_{2}$ with a general regular (triangle-free) graph, where the precolored
edges are required to be independent, were obtained.

In this paper, we continue the study of questions on precoloring extension of
cartesian products of graphs with a focus on iterated cartesian products of
graphs. Denote by $G^{d}$ the $d$th power of the cartesian product of $G$ with
itself. We pose the following question.

######  Problem 1.1.

Let $G$ be a graph where every precoloring of at most $\chi^{\prime}(G)-k$
edges, where $k\geq 1$, can be extended to a proper $\chi^{\prime}(G)$-edge
coloring. Is it true that every precoloring of at most
$\chi^{\prime}(G^{d})-k$ edges of $G^{d}$ can be extended to a
$\chi^{\prime}(G^{d})$-edge coloring of $G^{d}$?

The result of [7] for hypercubes deals with the case when $G=K_{2}$ (as well
as $G=C_{4}$), so a positive answer to Problem 1.1 would be a far-reaching
generalization of this result.

In this paper, we study Problem 1.1 for graphs with maximum degree two. We
verify that it has a positive answer for even as well as for odd cycles of
length at least $5$, and therefore also for paths. The case of odd cycles of
length $3$ appears to be more difficult, and it remains an open problem
whether Problem 1.1 has a positive answer in this case.

Even though any partial edge coloring of an odd cycle is extendable, we shall
restrict ourselves to the case when at most $\chi^{\prime}(G)-1$ edges in a
graph $G$ are precolored, since for all graphs except odd cycles and stars,
there are examples of partial edge colorings with $\chi^{\prime}(G)$
precolored edges that are not extendable. In fact, in [4] it was proved that
every partial $\chi^{\prime}(G)$-edge coloring of $G$ is extendable if and
only $G$ is isomorphic to a star $K_{1,n}$ or an odd cycle.

For even cycles, we additionally prove that any precoloring of a distance-$4$
matching in $C^{d}_{2k}$ is extendable to a proper $2k$-edge coloring. Here
the argument relies heavily on the fact that $C^{d}_{2k}$ is Class 1, and we
do not know whether a similar result hold for odd cycles.

##  2 Preliminaries

Before we prove our results, let us introduce some terminology and auxiliary
results.

If $\varphi$ is an edge precoloring of $G$ and an edge $e$ is colored under
$\varphi$, then we say that $e$ is $\varphi$-colored. A color $c$ appears at a
vertex $v$ under $\varphi$ if there is an edge incident with $v$ that is
colored $c$; otherwise, $c$ is missing at $v$.

If the edge coloring $\varphi$ uses $t$ colors and $1\leq a,b\leq t$, then a
path or cycle in $G$ is called $(a,b)$-colored under $\varphi$ if its edges
are colored by colors $a$ and $b$ alternately. We also say that such a path or
cycle is _bicolored under $\varphi$_. By switching colors $a$ and $b$ on a
maximal $(a,b)$-colored path or an $(a,b)$-colored cycle, we obtain another
proper $t$-edge coloring of $G$; this operation is called an interchange or a
swap.

In the above definitions, we often leave out the reference to an explicit
coloring $\varphi$, if the coloring is clear from the context.

If $G_{1}$ and $G_{2}$ are subgraphs of $G$, and $f_{i}$ is a proper edge
coloring of $G_{i}$, then we say that $f_{1}$ has no conflicts with $f_{2}$ if
no vertex is incident with two edges $e_{1}$ and $e_{2}$ such that
$f_{1}(e_{1})=f_{2}(e_{2})$.

By construction, $G=C^{d}_{r}$ decomposes into $d$ subgraphs, each consisting
of $r^{d-1}$ disjoint copies of $C_{r}$; these subgraphs are called
dimensions. Each subgraph of a dimension which is isomorphic to $C_{r}$ is
called a pillar, and each component of $G-E(D)$, where $D$ is a dimension, is
called a plane of $G$.

Two planes are adjacent if there is an edge with endpoints in both planes.
Similarly an edge $e$ not contained in a plane is incident to the plane if one
endpoint of $e$ is contained in the plane, and we say that a pillar edge is
between two planes if it is incident with both planes.

Two vertices of two distinct planes are corresponding if they are joined by an
edge; similarly for edges. Given edge colorings of two distinct planes, we say
that the planes are colored correspondingly if corresponding edges have the
same color.

We shall also need some standard definitions on list edge coloring. Given a
graph $G$, assign to each edge $e$ of $G$ a set $\mathcal{L}(e)$ of colors.
Such an assignment $\mathcal{L}$ is called a _list assignment_ for $G$ and the
sets $\mathcal{L}(e)$ are referred to as _lists_ or _color lists_. If all
lists have equal size $k$, then $\mathcal{L}$ is called a _$k$ -list
assignment_. Usually, we seek a proper edge coloring $\varphi$ of $G$, such
that $\varphi(e)\in\mathcal{L}(e)$ for all $e\in E(G)$. If such a coloring
$\varphi$ exists then $G$ is _$\mathcal{L}$ -colorable_ and $\varphi$ is
called an _$\mathcal{L}$ -coloring_. Denote by $\chi^{\prime}_{L}(G)$ the
minimum integer $t$ such that $G$ is $\mathcal{L}$-colorable whenever
$\mathcal{L}$ is a $t$-list assignment. If $\chi^{\prime}_{L}(G)\leq t$, then
$G$ is $t$-edge-choosable. The following lemmas are well-known and easy to
prove.

######  Lemma 2.1.

Every even cycle is $2$-edge-choosable.

######  Lemma 2.2.

If $L$ is a $2$-list assignment for the edges of an odd cycle $C$, then $C$ is
$L$-colorable, unless all lists are identical.

We shall also use the well-known proposition that paths are edge-list
colorable from a list assignment where every edge except the first one gets a
list of size at least two.

##  3 Extension of $2d-1$ precolored edges of $C^{d}_{2k}$

In this section, we prove the following theorem.

######  Theorem 3.1.

If $G=C^{d}_{2k}$ is the $d$th power of the cartesian product of the even
cycle $C_{2k}$ with itself, and $\varphi$ is a proper partial edge coloring of
$G$ with at most $2d-1$ precolored edges, then $\varphi$ can be extended to a
proper $2d$-edge coloring of $G$.

It is easily seen that the number of precolored edges here is best possible.

###### Proof of Theorem 3.1.

The proof proceeds by induction on $d$, the case $d=1$ being trivial. We shall
prove a series of lemmas that together will imply the theorem. In the proofs
of these lemmas we shall consider a specified dimension $D_{1}$, and the
subgraph $G-E(D_{1})$ consisting of $2k$ planes $Q_{1},\dots,Q_{2k}$, where
$Q_{i}$ is adjacent to $Q_{i+1}$ (here, and in the following, indices are
taken modulo $2k$).

We shall assume that every precoloring of a plane of $G-E(D_{1})$ with at most
$2d-3$ precolored edges is extendable to a proper edge coloring using $2d-2$
colors, and prove that a given precoloring $\varphi$ of $G$ with at most
$2d-1$ precolored edges is extendable to a proper $2d$-edge coloring of $G$.

We shall distinguish between the following cases, each of which is dealt with
in a lemma below.

  * •

There is a dimension of $G$ that contains no precolored edges.

  * •

Each dimension of $G$ contains precolored edges, and there is a dimension with
at most two precolored edges, the colors of which do not appear on edges in
any other dimension of $G$.

  * •

Every dimension of $G$ contains edges with colors that also appear on edges in
another dimension, or at least three precolored edges.

∎

######  Lemma 3.2.

If there is a dimension of $G$ that contains no precolored edges, then
$\varphi$ is extendable.

###### Proof.

Suppose that $D_{1}$ is a dimension in $G$ that contains no precolored edges,
and consider the subgraph $G-E(D_{1})$.

Suppose first that all precolored edges are contained in one plane, say
$Q_{1}$. Let $c_{1}$ and $c_{2}$ be two colors used by $\varphi$ (if just one
color appears under $\varphi$, then $c_{2}$ is any color from
$\\{1,\dots,2d\\}\setminus\\{c_{1}\\}$). From the restriction of $\varphi$ to
$Q_{1}$, we define an edge precoloring $\varphi^{\prime}$ of $Q_{1}$ by
removing the colors $c_{1}$ and $c_{2}$ from any edge of $Q_{1}$
$\varphi$-colored by these colors. Then, by the induction hypothesis,
$\varphi^{\prime}$ is extendable to a $(2d-2)$-coloring of $Q_{1}$ using
colors $\\{1,\dots,2d\\}\setminus\\{c_{1},c_{2}\\}$. Next we recolor the edges
$\varphi$-precolored $c_{1}$ and $c_{2}$ by these colors, and thereafter color
all other planes correspondingly. Thus, we can define a list assignment $L$
for the edges of $D_{1}$ by for each edge $e\in E(D_{1})$, letting $L(e)$ be
the set of all colors from $\\{1,\dots,2d\\}$ that do not appear on edges that
are adjacent to $e$. By Lemma 2.1, we can properly color the edges of $D_{1}$
from these lists to obtain a proper coloring that has no conflicts with the
coloring of $G-E(D_{1})$, and thus $\varphi$ is extendable.

Next, we consider the case when exactly two planes, say $Q_{1}$ and $Q_{i}$
contains all precolored edges. Since at most $2d-1$ colors appear under
$\varphi$, there is a color $c_{1}\in\\{1,\dots,2d\\}$ that is not used by
$\varphi$. Furthermore, let $c_{2}$ be a color appearing on some edge in the
plane with the largest number of precolored edges, say $Q_{1}$. Let
$\varphi^{\prime}$ be the coloring obtained from $\varphi$ by removing color
$c_{2}$ from any edge colored $c_{2}$ under $\varphi$. Then the restrictions
of $\varphi^{\prime}$ to $Q_{1}$ and $Q_{i}$, respectively, are extendable to
proper $(2d-2)$-edge colorings using colors
$\\{1,\dots,2d\\}\setminus\\{c_{1},c_{2}\\}$. By recoloring any edge
$\varphi$-colored $c_{2}$ by the color $c_{2}$, we obtain proper edge
colorings $f_{1}$ and $f_{i}$ of $Q_{1}$ and $Q_{i}$, respectively.

Now, either $i\neq 2$ or $i\neq 2k$; suppose the former holds. Then we color
$Q_{2}$ correspondingly to how $Q_{1}$ is colored under $f_{1}$, and we color
all other uncolored $Q_{j}$’s correspondingly to how $Q_{i}$ is colored under
$f_{i}$. Now, since $Q_{2j-1}$ and $Q_{2j}$ are colored correspondingly, for
every edge $e$ with one endpoint in $Q_{2j-1}$ and one endpoint in $Q_{2j}$,
there is a color $\\{1,\dots,2d\\}\setminus\\{c_{1}\\}$ that does not appear
at an endpoint of $e$. Thus, by coloring all such edges by such a color and
then coloring all other edges of $D_{1}$ by the color $c_{1}$, we obtain an
extension of $\varphi$.

Lastly, let us consider the case when at least three planes contains all
precolored edges. As before, let $c_{1}$ be a color that is not used by
$\varphi$. Since at least three planes contains precolored edges, each plane
contains at most $2d-3$ precolored edges, and two adjacent planes contain
precolored edges from at most $2d-2$ colors. This implies that for each
$j=1,\dots,k$ there is a color $c^{\prime}_{j}$ in
$\\{1,\dots,2d\\}\setminus\\{c_{1}\\}$ that is not used in the restriction of
$\varphi$ to $Q_{2j-1}$ and $Q_{2j}$. Thus for $j=1,\dots,k$, we can extend
the restriction of $\varphi$ to $Q_{2j-1}$ and $Q_{2j}$ using the $2d-2$
colors in $\\{1,\dots,2d\\}\setminus\\{c_{1},c^{\prime}_{j}\\}$. For
$j=1,\dots k$, we then color all edges of $D_{1}$ between $Q_{2j-1}$ and
$Q_{2j}$ by $c^{\prime}_{j}$, and all other edges of $D_{1}$ by the color
$c_{1}$. This yields an extension of $\varphi$. ∎

######  Lemma 3.3.

If each dimension of $G$ contains precolored edges and there is a dimension
with at most two precolored edges, the colors of which do not appear on edges
in any other dimension of $G$, then $\varphi$ is extendable.

###### Proof.

Assume first that there is a dimension $D_{1}$ containing only one precolored
edge and that there is a plane $Q_{1}$ in $G-E(D_{1})$ containing all other
precolored edges. Suppose that the precolored edge of $D_{1}$ is colored
$c_{1}$. As in the proof of the preceding lemma, there is an extension of the
restriction of $\varphi$ to $Q_{1}$ using colors
$\\{1,\dots,2d\\}\setminus\\{c_{1}\\}$. Next, we color all other planes of
$G-E(D_{1})$ correspondingly, which implies that every edge of $D_{1}$ is
adjacent to edges of $2d-2$ different colors, so by Lemma 2.1, $\varphi$ is
extendable.

Let us now consider the case when there is no such dimension containing only
one precolored edge and a plane containing all other precolored edges. Let
$D_{1}$ be a dimension containing at most two edges that are precolored by
colors not appearing on any other edges under $\varphi$. Our assumption
implies that every plane in $G-E(D_{1})$ contains at most $2d-3$ precolored
edges, and that there are two colors $c_{1},c_{2}$ that do not appear on any
edge in $G-E(D_{1})$, and at most two edges of $D_{1}$ are colored by colors
from $\\{c_{1},c_{2}\\}$.

Suppose first that there is an extension of the restriction of $\varphi$ to
$D_{1}$ using colors $c_{1}$ and $c_{2}$. Since every plane in $G-E(D_{1})$
contains at most $2d-3$ precolored edges, every plane has a proper edge
coloring using colors $\\{1,\dots,2d\\}\setminus\\{c_{1},c_{2}\\}$ that agrees
with $\varphi$. Hence, $\varphi$ is extendable.

Suppose now that the restriction of $\varphi$ to $D_{1}$ is not extendable
using colors $c_{1}$ and $c_{2}$. Then there are at least two precolored edges
in $D_{1}$, and so $G-E(D_{1})$ contains at most $2d-3$ precolored edges and
there is a color $c_{3}\in\\{1,\dots,2d\\}\setminus\\{c_{1},c_{2}\\}$ that
does not appear on any edge under $\varphi$.

Since the restriction of $\varphi$ to $D_{1}$ is not extendable, there are
planes $Q_{1},Q_{2},\dots,Q_{i}$ in $G-E(D_{1})$ such that $Q_{1}$ and $Q_{i}$
are incident with precolored edges of $D_{1}$ and $Q_{2},\dots,Q_{i-1}$ are
not. Without loss of generality we assume that $Q_{1}$ is incident with an
edge of $Q_{1}$ that is precolored $c_{1}$. We take an extension of $Q_{1}$
using colors $\\{1,\dots,2d\\}\setminus\\{c_{1},c_{3}\\}$, and for
$j=2,\dots,i-1$, we take an extension of the restriction of $\varphi$ to
$Q_{j}$ using colors $\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$. Moreover,
we color every path in $D_{1}$ with vertices in $Q_{1},\dots,Q_{i}$ using
colors $c_{3}$ and $c_{2}$ alternately, and starting with $c_{3}$ at $Q_{1}$.

If $Q_{i}$ is incident with an edge of $D_{1}$ colored $c_{2}$, then $i$ is
even, and we take extensions of the restriction of $\varphi$ to $Q_{i}$ and
$Q_{i+1}$ using colors $\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$, and for
$j=i+2,\dots,2d$, we take extensions of the restrictions of $\varphi$ to
$Q_{j}$ using colors $\\{1,\dots,2d\\}\setminus\\{c_{1},c_{3}\\}$. Moreover,
we color every path in $D_{1}$ with vertices in $Q_{i+1},\dots,Q_{2k}$ using
colors $c_{3}$ and $c_{1}$ alternately, and starting with $c_{3}$ at
$Q_{i+1}$. Finally, we color all edges between $Q_{1}$ and $Q_{2k}$ by the
color $c_{1}$, and all edges between $Q_{i}$ and $Q_{i+1}$ by the color
$c_{2}$. This yields an extension of $\varphi$.

If $Q_{i}$ is incident with an edge colored $c_{1}$, then $i$ is odd, and we
proceed similarly, but take extensions of the restrictions of $\varphi$ to
$Q_{i}$ and $Q_{i+1}$ using colors
$\\{1,\dots,2d\\}\setminus\\{c_{1},c_{2}\\}$, for $j=i+2,\dots 2k-1$, we take
extensions of the restrictions of $\varphi$ to $Q_{j}$ using colors
$\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$, and an extension of the
restriction of $\varphi$ to $Q_{2k}$ using colors
$\\{1,\dots,2d\\}\setminus\\{c_{1},c_{3}\\}$. We then color the paths of
$D_{1}$ so that the resulting coloring is proper and agrees with $\varphi$. ∎

######  Lemma 3.4.

If each dimension of $G$ contains edges with colors that also appear on edges
in another dimension, or at least three precolored edges, then $\varphi$ is
extendable.

###### Proof.

Since at most $2d-1$ edges are precolored, there is a dimension $D_{1}$ with
just one precolored edge $e$. Suppose $\varphi(e)=c_{1}$. Since at least one
color appears on at least two edges, there are two colors
$c_{2},c_{3}\in\\{1,\dots,2d\\}\setminus\\{c_{1}\\}$ that do not appear on any
edge under $\varphi$.

We consider some different cases.

Case 1. All precolored edges except $e$ lie in the same plane:

Let $Q_{1}$ be a plane containing all precolored edges except $e$. By removing
the color from every edge of $Q_{1}$ that is $\varphi$-colored $c_{1}$, we
obtain a precoloring that by the induction hypothesis is extendable to a
proper edge coloring of $Q_{1}$ using colors
$\\{1,\dots,2d\\}\setminus\\{c_{1},c_{2}\\}$. Denote this coloring by $f$. By
recoloring the edges of $Q_{1}$ that are $\varphi$-colored $c_{1}$, we obtain,
from $f$, an extension $f^{\prime}$ of the restriction of $\varphi$ to
$Q_{1}$. We color all other planes of $G-E(D_{1})$ correspondingly.

Suppose first that $e$ is incident with $Q_{1}$. Then, by Lemma 2.1, there is
proper edge coloring $g$ of $D_{1}$ that has no conflicts with $f^{\prime}$.
Moreover, since just one edge of $D_{1}$ is precolored, we can choose this
coloring so that $g(e)=c_{1}$. Hence, $\varphi$ is extendable.

Next, we consider the case when $e$ is not incident with $Q_{1}$. Let $C$ be
the cycle in $D_{1}$ containing $e$. If no vertex of $C$ is incident with an
edge colored $c_{1}$ under $f^{\prime}$, then we may proceed as in the
preceding paragraph. Otherwise, the endpoints of $e$ are incident with two
edges $e_{1}$ and $e_{2}$ of $G-E(D_{1})$ colored $c_{1}$. Note that
$e,e_{1},e_{2}$ are contained in a $4$-cycle in $G$, the fourth edge of which
we denote by $e_{3}$. As before, we properly color the edges of $D_{1}$ so
that the resulting coloring $g^{\prime}$ of $G$ is proper. Moreover, we choose
$g^{\prime}$ so that $g^{\prime}(e)=g^{\prime}(e_{3})=c_{2}$. By swapping
colors on the bicolored $4$-cycle with edges $e,e_{1},e_{2},e_{3}$ we finally
obtain an extension of $\varphi$.

Case 2. All precolored edges except $e$ lie in exactly two planes:

Let $Q_{1}$ and $Q_{i}$ be the two planes containing the precolored edges
distinct from $e$.

Suppose first that $e$ is not adjacent to $Q_{1}$ or $Q_{i}$. Since each of
$Q_{1}$ and $Q_{i}$ contains at most $2d-3$ precolored edges, there are
extensions $f_{1}$ and $f_{i}$ of the restrictions of $\varphi$ to $Q_{1}$ and
$Q_{i}$, respectively, using colors
$\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$. Next, we properly color each
plane $Q$ of $G-E(D_{1})$ that is distinct from $Q_{1}$ and $Q_{i}$, by colors
$\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$, so that all these planes are
colored correspondingly. Moreover, color all edges of $D_{1}$ alternately
using colors $c_{2}$ and $c_{3}$ and starting with color $c_{2}$ for all edges
of $D_{1}$ with endpoints in $Q_{1}$ and $Q_{2}$. Then $e$ is contained in a
bicolored $4$-cycle, and by swapping colors on this cycle, we obtain an
extension of $\varphi$.

Let us now consider the case when $e$ is adjacent to exactly one of $Q_{1}$
and $Q_{i}$. Suppose e.g. that $e$ is incident with $Q_{1}$ and $Q_{2}$, so
$i\neq 2$. Since each of $Q_{1}$ and $Q_{i}$ contains at most $2d-3$
precolored edges, there are extensions $f_{1}$ and $f_{i}$ of the restrictions
of $\varphi$ to $Q_{1}$ and $Q_{i}$, respectively, using colors
$\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$. Next, we color all uncolored
planes in $G-E(D_{1})$ correspondingly to how $Q_{1}$ is colored, color all
cycles of $D_{1}$ properly using colors $c_{2}$ and $c_{3}$, and starting with
color $c_{2}$ for all edges with endpoints in $Q_{1}$ and $Q_{2}$. Since
$Q_{1}$ and $Q_{2}$ are colored correspondingly, there is a bicolored
$4$-cycle with colors $c_{1},c_{2}$ containing $e$. By swapping colors on this
$4$-cycle, we obtain an extension of $\varphi$.

Suppose now that $e_{1}$ is incident with both planes containing precolored
edges, say $Q_{1}$ and $Q_{2}$. By removing the color from any edge that is
colored $c_{1}$ under $\varphi$, we obtain a precoloring $\varphi^{\prime}$ of
$G$ such that the restrictions of $\varphi^{\prime}$ to $Q_{1}$ and $Q_{2}$,
respectively, are extendable to proper edge colorings using colors
$\\{1,\dots,2d\\}\setminus\\{c_{1},c_{3}\\}$. By recoloring any edge of
$Q_{1}$ and $Q_{2}$ that is $\varphi$-colored $c_{1}$, we obtain proper edge
colorings $f_{1}$ and $f_{2}$ of $Q_{1}$ and $Q_{2}$, respectively, using
colors $\\{1,\dots,2d\\}\setminus\\{c_{3}\\}$. We color the edges of $D_{1}$
between $Q_{1}$ and $Q_{2}$ by $c_{3}$, except for $e$ which is colored
$c_{1}$.

Next, we color $Q_{3},\dots,Q_{2k-1}$ correspondingly to how $Q_{2}$ is
colored under $f_{2}$ and $Q_{2k}$ correspondingly to how $Q_{1}$ is colored.
Now, since $Q_{2}$ and $Q_{3}$ are colored correspondingly, for each edge
$e^{\prime}$ of $D_{1}$ between $Q_{2}$ and $Q_{3}$, there is a color
$c^{\prime}\in\\{1,\dots,2d\\}$ that does not appear on an adjacent edge in
$Q_{2}$ or on the edge between $Q_{1}$ and $Q_{2}$. We color every such edge
$e^{\prime}$ between $Q_{2}$ and $Q_{3}$ by such a color $c^{\prime}$, and
thereafter color all edges of every path of $D_{1}$ from $Q_{1}$ to $Q_{2k}$
alternately by the colors used on the edges between $Q_{1}$ and $Q_{2}$, and
$Q_{2}$ and $Q_{3}$ respectively. This yields a proper partial edge coloring
where the endpoints of every edge of $D_{1}$ between $Q_{1}$ and $Q_{2k}$ are
incident to edges with $2d-1$ colors from $\\{1,\dots,2d\\}$. Thus we can
properly color every such edge so that we get an extension of $\varphi$ using
colors $1,\dots,2d$.

Case 3. At least three planes in $G-E(D_{1})$ contains precolored edges:

The assumption implies that every plane in $G-E(D_{1})$ contains at most
$2d-4$ precolored edges, and any two adjacent planes contains at most
altogether $2d-3$ precolored edges. Without loss of generality, we assume that
$e$ is incident with $Q_{1}$ and $Q_{2}$. Since every vertex of $Q_{1}$ and
$Q_{2}$ has degree $2d-2$, and $Q_{1}\cup Q_{2}$ contains at most $2d-3$
precolored edges, there are uncolored corresponding edges $e_{1}\in E(Q_{1})$
and $e_{2}\in E(Q_{2})$ that are adjacent to $e$ but not to any edge in
$Q_{1}\cup Q_{2}$ precolored $c_{1}$. From the restriction of $\varphi$ to
$G-E(D_{1})$, we define a new precoloring $\varphi^{\prime}$ of $G-E(D_{1})$
by in addition coloring $e_{1}$ and $e_{2}$ by the color $c_{1}$.

Now, since each component of $G-E(D_{1})$ contains at most $2d-3$
$\varphi^{\prime}$-precolored edges, by the induction hypothesis, there is an
extension of $\varphi^{\prime}$ to $G-E(D_{1})$ using colors
$\\{1,\dots,2d\\}\setminus\\{c_{2},c_{3}\\}$. Next, we properly color the
edges of $D_{1}$ using colors $c_{2}$ and $c_{3}$, and starting with color
$c_{2}$ for the edges with endpoints in $Q_{1}$ and $Q_{2}$. Now, since
$e_{1}$ and $e_{2}$ are both colored $c_{1}$, there is a bicolored $4$-cycle
with edges $e_{1},e_{2}$ and $e$ with colors $c_{1}$ and $c_{2}$. By swapping
colors on this $4$-cycle, we obtain an extension of $\varphi$. ∎

##  4 Extending a precoloring of $2d$ edges in $C^{d}_{2k+1}$

In this section, we prove the following theorem for the iterated cartesian
product of odd cycles of length at least $5$.

######  Theorem 4.1.

If $G=C^{d}_{2k+1}$ is the $d$th power of the cartesian product of the odd
cycle $C_{2k+1}$ with itself ($k\geq 2$), and $\varphi$ is a proper partial
edge coloring of $G$ with at most $2d$ precolored edges, then $\varphi$ can be
extended to a proper $(2d+1)$-edge coloring of $G$.

As in the case of even cycles, (for $d\geq 2$) it is easily seen that the
number of precolored edges here is best possible.

###### Proof of Theorem 4.1.

The proof of this theorem is similar to the proof of Theorem 3.1, so we shall
omit or just sketch some parts which are similar to techniques in that proof.
Particularly in the last parts of the proof, to avoid tedious repetition we
omit parts which are very similar to techniques that have been described in
more detail earlier in the proof.

We proceed by induction on $d$, the case $d=1$ being trivial. As in the proof
of Theorem 3.1, we shall prove a series of lemmas that together will imply the
theorem. Since odd cycles are not $2$-edge-colorable, the proof is longer and
more difficult than the proof of that theorem. In the proofs of these lemmas
we shall consider a specified dimension $D_{1}$, and the subgraph $G-E(D_{1})$
consisting of $2k+1$ planes $Q_{1},\dots,Q_{2k+1}$, where $Q_{i}$ is adjacent
to $Q_{i+1}$ (here, and in the following, indices are taken modulo $2k+1$).

We shall assume that every edge precoloring of a plane of $G-E(D_{1})$ with at
most $2d-2$ precolored edges is extendable to a proper edge coloring using
$2d-1$ colors, and prove that a given precoloring $\varphi$ of $G$ with at
most $2d$ precolored edges is extendable to a proper $(2d+1)$-edge coloring of
$G$. To that end, we shall distinguish between the following different cases.

  * •

There is a dimension of $G$ that contains no precolored edges.

  * •

Every dimension of $G$ contains precolored edges, and there is a dimension
with at most two precolored edges, the colors of which do not appear on edges
in any other dimension of $G$.

  * •

Every dimension of $G$ contains edges with colors that also appear on edges in
other dimensions, or at least three precolored edges, and one dimension
contains only one precolored edge.

  * •

Every dimension of $G$ contains two precolored edges, at least one of which
has a color appearing on edges in another dimension.

∎

######  Lemma 4.2.

If there is a dimension of $G$ that contains no precolored edges, then
$\varphi$ is extendable.

###### Proof.

Suppose that $D_{1}$ is a dimension in $G$ that contains no precolored edges.
We consider some different cases.

Case 1. All precolored edges are contained in one plane:

Suppose that all precolored edges are contained in one plane, say $Q_{1}$. Let
$c_{1}$ and $c_{2}$ be two colors used by $\varphi$ (if just one color appears
under $\varphi$, then $c_{2}$ is any color from
$\\{1,\dots,2d+1\\}\setminus\\{c_{1}\\}$). By removing the colors $c_{1}$ and
$c_{2}$ from any edge colored by these colors, we obtain an edge precoloring
$\varphi^{\prime}$ of $Q_{1}$ that is extendable to a $(2d-1)$-coloring of
$Q_{1}$ using colors $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$. Next we
recolor the edge precolored $c_{1}$ and $c_{2}$, respectively, using these
colors, and thereafter color all other planes correspondingly. Since all
planes are colored correspondingly, we can apply Lemma 2.2 to properly color
the edges of each pillar of $D_{1}$ to obtain an extension of $\varphi$.

Case 2. All precolored edges are contained in two planes:

Suppose that $Q_{1}$ and $Q_{i}$ contains all precolored edges. We shall
consider three different cases.

Suppose first that $2d-1$ precolored edges are contained in the same plane,
say $Q_{1}$, and that one edge $e_{i}$ in $Q_{i}$ is colored $c_{1}$. Let
$c_{2}$ be a color appearing on some edge in $Q_{1}$. From the restriction of
$\varphi$ to $Q_{1}$ we define a precoloring $\varphi^{\prime}$ of $Q_{1}$ by
removing color $c_{2}$ from every edge $\varphi$-colored $c_{2}$. Then
$\varphi^{\prime}$ is extendable to a proper $(2d-1)$-edge coloring using
$2d-1$ colors from $\\{1,\dots 2d+1\\}\setminus\\{c_{2}\\}$. By recoloring
every edge of $Q_{1}$ that is $\varphi$-colored $c_{2}$ by the color $c_{2}$,
we obtain a proper edge coloring $f$ of $Q_{1}$.

Let $e_{1}$ be the edge of $Q_{1}$ corresponding to $e_{i}$ of $Q_{i}$. If
$f(e_{1})=c_{1}$, then we color all planes in $G-E(D_{1})$ correpondingly to
how $Q_{1}$ is colored. By Lemma 2.2, we may then color the edges of $D_{1}$
to obtain an extension of $\varphi$. If, on the other hand,
$f(e_{1})=c_{3}\neq c_{1}$, then we define a proper edge coloring of $Q_{i}$
by coloring it correspondingly to $Q_{1}$ but permuting the colors in
$\\{1,\dots,2d+1\\}$ so that $c_{1}$ is mapped to $c_{3}$ and vice versa, and
all other colors are mapped to themselves. This yields a proper edge coloring
of $Q_{i}$ that agrees with the restriction of $\varphi$ to $Q_{i}$. We color
all other $Q_{j}$’s correspondingly to how $Q_{i}$ is colored, and applying
Lemma 2.2, we obtain an extension of $\varphi$, as before.

Let us now assume that both $Q_{1}$ and $Q_{i}$ contain at most $2d-2$
precolored edges, respectively, and at most $2d-1$ colors, say $1,\dots,2d-1$,
are used by $\varphi$. By the induction hypothesis, the restrictions of
$\varphi$ to $Q_{1}$ to $Q_{i}$ are extendable to $(2d-1)$-edge colorings
$f_{1}$ and $f_{i}$, respectively, using colors $1,\dots,2d-1$. We color all
other $Q_{j}$’s correspondingly to how $Q_{i}$ is colored, and using Lemma 2.2
we obtain an extension of $\varphi$.

On the other hand, if both $Q_{1}$ and $Q_{i}$ contains at most $2d-2$
precolored edges, respectively, but in total $2d$ colors $1,\dots,2d$ are used
by $\varphi$, then every color appears on exactly one edge under $\varphi$.
Hence, we may assume that one edge of $Q_{1}$, but not $Q_{i}$, is colored,
say, $1$, and similarly, one edge of $Q_{i}$ is colored $2d$. By the induction
hypothesis, there is an extension $f_{1}$ of the restriction of $\varphi$ to
$Q_{1}$ using colors $1,\dots,2d-1$, and an extension $f_{i}$ of the
restriction of $\varphi$ to $Q_{i}$ using colors $2,\dots,2d$.

Now, either $i\neq 2$ or $i\neq 2k+1$; suppose that the former holds. We
define a proper edge coloring $f_{2}$ of $Q_{2}$ using colors $2,\dots,2d$ by
coloring $Q_{2}$ correspondingly to $Q_{1}$ but using color $2d$ instead of
$1$, and then coloring all other planes of $G-E(D_{1})$ correspondingly to how
$Q_{i}$ is colored. By the construction of $f_{2}$, for each pillar edge $e$
of $D_{1}$ between $Q_{1}$ and $Q_{2}$, there is a color in $\\{2,\dots,2d\\}$
that does not appear at an endpoint of $e$. We color every such pillar edge by
this color, and then color the edges of every cycle in $D_{1}$ by colors $1$
and $2d+1$ alternately, and starting with color $1$ at $Q_{2}$. This yields an
extension of $\varphi$.

Case 3. All precolored edges are contained in at least three planes:

Let $Q_{j_{1}},Q_{j_{2}},\dots,Q_{j_{s}}$ be the planes of $G-E(D_{1})$ that
contain precolored edges, where $j_{1}\leq j_{2}\leq\dots\leq j_{s}$. Note
that any two planes contain precolored edges of altogether at most $2d-1$
colors, and that there are two planes $Q_{j_{i}}$ and $Q_{j_{i+1}}$ that
contain precolored edges of altogether at most $2d-2$ colors. We assume that
$Q_{j_{1}}$ and $Q_{j_{s}}$ are two such planes.

Consider an arbitrary cycle $C$ in $D_{1}$. We partition the edges of $C$ into
paths $P_{12},\dots,P_{(s-1)s},P_{s1}$ where $P_{r(r+1)}$ has its endpoints in
$Q_{j_{r}}$ and $Q_{j_{r+1}}$. Now, for each path $P_{r(r+1)}$, there are two
colors $c_{r(r+1)},c^{\prime}_{r(r+1)}\in\\{1,\dots,2d+1\\}$ so that none of
these colors appear in the restriction of $\varphi$ to $Q_{j_{r}}\cup
Q_{j_{r+1}}$. For $r=1,\dots s-1$, we color each path $P_{r(r+1)}$ alternately
by colors $c_{r(r+1)}$ and $c^{\prime}_{r(r+1)}$, so that the resulting edge
coloring is proper. Now, by assumption we have that $Q_{j_{1}}$ and
$Q_{j_{s}}$ contain edges of altogether at most $2d-2$ colors. Hence, there
are two colors $c$ and $c^{\prime}$ that do not appear on edges in $Q_{j_{1}}$
or $Q_{j_{s}}$, nor on an edge of $D_{1}$ that is incident with $Q_{j_{1}}$.
We color the edges in the path of $C$ from $Q_{j_{s}}$ to $Q_{j_{1}}$ by
colors $c$ and $c^{\prime}$ so that the resulting coloring is proper.

Next, we color all uncolored edges of $D_{1}$ correspondingly to how $C$ is
colored. Now, each $Q_{j}$ is incident with edges of $D_{1}$ of two colors
that do not appear on edges of $Q_{j}$ under $\varphi$, and, moreover, each
$Q_{j}$ contains at most $2d-2$ precolored edges. Hence, by the induction
hypothesis, the restriction of $\varphi$ to each $Q_{j}$ can be extended to a
proper edge coloring using colors that do not appear on edges of $D_{1}$ that
are incident with $Q_{j}$. In conclusion, $\varphi$ is extendable. ∎

######  Lemma 4.3.

If there is a dimension of $G$ with at most two precolored edges, the colors
of which do not appear on edges in any other dimension of $G$, then $\varphi$
is extendable.

###### Proof.

Let $D_{1}$ be a dimension containing at most two precolored edges, the colors
of which do not appear on any edges in $G-E(D_{1})$.

We first consider the case when only one color $c_{1}$ appears on the
precolored edges of $D_{1}$.

Case A. Only one color $c_{1}$ appears on the precolored edge(s) of $D_{1}$:

In this case the argument breaks into several subcases.

Case 1. All precolored edges of $G-E(D_{1})$ are contained in one plane:

Let $Q_{1}$ be a plane in $G-E(D_{1})$ containing all precolored edges except
the ones of $D_{1}$. As before, there is an extension of the restriction of
$\varphi$ to $Q_{1}$ using colors $\\{1,\dots,2d+1\\}\setminus\\{c_{1}\\}$ (by
removing the colors of edges colored by some color $c_{2}\neq c_{1}$, taking
an extension of the resulting precoloring of $Q_{1}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ and then recoloring the edges
that are $\varphi$-colored $c_{2}$). Next, we color all other planes of
$G-E(D_{1})$ correspondingly. Now, since all planes of $G-E(D_{1})$ are
colored correspondingly, every edge of $D_{1}$ is adjacent to edges of $2d-2$
different colors, so by Lemma 2.2, $\varphi$ is extendable.

Case 2. All precolored edges of $G-E(D_{1})$ are contained in two planes:

Since at most two edges of $D_{1}$ are precolored, and only two planes contain
precolored edges, there are two planes $Q_{j}$ and $Q_{j+1}$, at most one of
which contains precolored edges, and such that there is no precolored edge
between $Q_{j}$ and $Q_{j+1}$. Suppose e.g. $Q_{j+1}$ contains no precolored
edges. Let $c_{2}\in\\{1,\dots,2d+1\\}$ be a color such that no edge of $G$ is
precolored $c_{2}$. We take an extension of the restriction of $\varphi$ to
$Q_{j}$ using colors $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$, color
$Q_{j+1}$ correspondingly, and then color all edges between $Q_{j}$ and
$Q_{j+1}$ by the unique color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ missing at its endpoints. Now,
unless there are two precolored edges of $D_{1}$ that are contained in the
same pillar $P$ and at even distance in the path $P^{\prime}$ obtained from
$P$ by removing the edge between $Q_{j}$ and $Q_{j+1}$, we can color all edges
of $D_{1}$ alternately by colors $c_{1}$ and $c_{2}$, and then color all
remaining planes of $Q-E(D_{1})$ by colors in
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ so that the resulting edge
coloring is proper and agrees with $\varphi$.

Alternatively, if the two precolored edges of $D_{1}$ have even distance in
$P^{\prime}$, then we select two additional planes $Q_{r}$ and $Q_{r+1}$,
containing no precolored edges between them and such that at most one of
$Q_{r}$ and $Q_{r+1}$ contains precolored edges. We may then repeat the above
coloring procedure for $Q_{r}$ and $Q_{r+1}$; we leave the details to the
reader.

Case 3. All precolored edges of $G-E(D_{1})$ are contained in at least three
planes:

Suppose first that there is only one precolored $e$ of $G-E(D_{1})$, and let
$Q_{j_{1}},Q_{j_{2}},\dots,Q_{j_{s}}$ be the planes of $G-E(D_{1})$ that
contain precolored edges, where $j_{1}\leq j_{2}\leq\dots\leq j_{s}$. Note
that any two planes contain precolored edges of altogether at most $2d-2$
colors. Now as in Case 3 of the proof of the preceding lemma, we color the
edges of the paths between pairs of planes with precolored edges by picking
two colors that do not appear in the restrictions of $\varphi$ to these
planes. Naturally, we pick these colors so that in the path containing $e$,
the resulting coloring agrees with $\varphi$. Thereafter, we take extensions
of the restrictions of $\varphi$ to the planes
$Q_{j_{1}},Q_{j_{2}},\dots,Q_{j_{s}}$, so that the resulting coloring is
proper. Hence, $\varphi$ is extendable.

Suppose now that $G-E(D_{1})$ contains two precolored edges $e_{1}$ and
$e_{2}$. Then there are colors $c_{2},c_{3}$ that do not appear on any edges
of $G$ under $\varphi$.

Now, if $e_{1}$ and $e_{2}$ are corresponding edges or are not incident with a
common plane, then we may proceed as in the preceding paragraph, but possibly
pick three colors when coloring the paths between planes with precolored edges
to ensure that the obtained coloring of $D_{1}$ is proper and agrees with
$\varphi$. This is possible since any two planes contain at most $2d-3$
precolored edges.

It remains to consider the case when $e_{1}$ and $e_{2}$ are incident with
exactly one common plane $Q_{1}$. Suppose that $e_{1}$ in addition is incident
with $Q_{2}$. If there are at most $2d-4$ precolored edges in $Q_{1}\cup
Q_{2}$ and at most $2d-4$ precolored edges in $Q_{2k+1}\cup Q_{1}$, then there
are independent edges $e^{\prime}_{1}$ and $e^{\prime}_{2}$ in $Q_{1}$,
adjacent to $e_{1}$ and $e_{2}$, respectively, and such that neither these
edges, nor the corresponding edges of $Q_{2}$ and $Q_{2k+1}$, respectively,
are precolored. From the restriction of $\varphi$ to $Q_{2k+1}\cup Q_{1}\cup
Q_{2}$, we define a precoloring $\varphi^{\prime}$ by coloring all these four
edges of $Q_{2k+1}\cup Q_{1}\cup Q_{2}$ by the color $c_{1}$. We may now
obtain an extension of $\varphi^{\prime}$ by proceeding as in Case 3 of the
preceding lemma, and thereafter swap colors on two bicolored $4$-cycles
containing $e_{1}$ and $e_{2}$, respectively, to obtain an extension of
$\varphi$.

Suppose now instead that $Q_{1}\cup Q_{2k+1}$, say, contains exactly $2d-3$
precolored edges. If there exist independent edges $e^{\prime}_{1}$ and
$e^{\prime}_{2}$ in $Q_{1}$, as described in the preceding paragraph, then we
may proceed as in that case, so suppose that there are no two such edges.

Then, since both $Q_{2k+1}\cup Q_{1}$ and $Q_{1}\cup Q_{2}$ contains at most
$2d-3$ precolored edges and every $Q_{j}$ is $(2d-2)$-regular, the endpoints
of $e_{1}$ and $e_{2}$ in $Q_{1}$ must be adjacent. Now, it is easy to see
that this implies that there is either an edge $e^{\prime}_{1}$ adjacent to
$e_{1}$ but not to $e_{2}$, such that $e^{\prime}_{1}$ and the corresponding
edge of $Q_{2}$ are not precolored, or an uncolored edge $e^{\prime}_{2}$
adjacent to $e_{2}$ but not to $e_{1}$, and such that $e^{\prime}_{2}$ and the
corresponding edge of $Q_{2k+1}$ are not precolored. Suppose, for instance,
that such an edge $e^{\prime}_{1}$ exists.

Consider the precoloring $\varphi^{\prime}$ obtained from the restriction of
$\varphi$ to $Q_{2k+1}\cup Q_{1}\cup Q_{2}$ by in addition coloring
$e^{\prime}_{1}$ and also the corresponding edge of $Q_{2}$ by the color
$c_{1}$. Now, since there is no uncolored edge $e^{\prime}_{2}$ as described
above, it follows that all $d-2$ edges $a_{1},\dots,a_{d-2}$ adjacent to
$e_{2}$ in $Q_{1}$ satisfies that either $a_{i}$, or the corresponding edge of
$Q_{2k+1}$, is $\varphi^{\prime}$-precolored or adjacent to an edge colored
$c_{1}$ under $\varphi^{\prime}$. Moreover, since $Q_{2k+1}\cup Q_{1}$ is
triangle-free and contains at most $2d-2$ $\varphi^{\prime}$-precolored edges,
every precolored edge of $Q_{2k+1}\cup Q_{1}$ satisfies this condition. Thus
by properly coloring the uncolored edges adjacent to $e_{2}$, except the one
adjacent to $e_{1}$, by colors from
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2},c_{3}\\}$, we obtain a precoloring
$\varphi^{\prime\prime}$ from $\varphi^{\prime}$. Then every plane in
$G-E(D_{1})$ contains at most $2d-2$ precolored edges under
$\varphi^{\prime\prime}$. Furthermore any extension of the restriction of
$\varphi^{\prime\prime}$ to $Q_{2k+1}\cup Q_{1}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$ does not use $c_{1}$ on an edge
adjacent to $e_{2}$. Now, since there is exactly one precolored edge of
$G-E(D_{1})$ that is not contained in $Q_{2k+1}\cup Q_{1}$, we may once again
proceed as in Case 3 of Lemma 4.2 and color the edges of $D_{1}$ appropriately
to obtain an extension of $\varphi^{\prime\prime}$ where no edge adjacent to
$e_{2}$ is colored $c_{1}$. Thereafter we may swap colors on a bicolored
$4$-cycle and recolor $e_{2}$ to obtain an extension of $\varphi$.

Case B. The precolored edges of $D_{1}$ are colored differently:

Suppose now that $D_{1}$ contains two precolored edges, colored $c_{1}$ and
$c_{2}$, respectively, and that $c_{3}$ is a color that does not appear on any
edge under $\varphi$. If there is an extension of the restriction of $\varphi$
to $D_{1}$ using colors $\\{c_{1},c_{2},c_{3}\\}$, such that all edges of
$D_{1}$ are colored correspondingly, then there are extensions of the
restrictions of $\varphi$ to all the planes $G-E(D_{1})$ using colors that do
not appear on incident edges of $D_{1}$. Hence, $\varphi$ is extendable.

On the other hand, if there is no such extension of the restriction of
$\varphi$, then the two precolored edges $e_{1}$ and $e_{2}$ of $D_{1}$ are
incident with the same pair of planes, $Q_{1}$ and $Q_{2}$ say. Now, if
$Q_{1}\cup Q_{2}$ contains at most $2d-4$ precolored edges, then there are
uncolored corresponding edges $e^{\prime}_{1}\in E(Q_{1})$ and
$e^{\prime}_{2}\in E(Q_{2})$ that are adjacent to $e_{2}$, but not to $e_{1}$.
We may now color these edges $c_{2}$ and remove the color from $e_{2}$ to
obtain the precoloring $\varphi^{\prime}$ from $\varphi$, and then proceed as
in Case 3 when only one edge of $D_{1}$ is precolored to obtain an extension
of $\varphi^{\prime}$. Thereafter we swap colors on a bicolored $4$-cycle to
obtain an extension of $\varphi$.

If, on the other hand, $Q_{1}\cup Q_{2}$ contains at least $2d-3$ precolored
edges, then there is at most one edge in $G-E(D_{1})\cup E(Q_{1})\cup
E(Q_{2})$ that is precolored. Without loss of generality, we assume that
$Q_{3}$ contains no precolored edge. By the induction hypothesis, there is an
extension of the restriction of $\varphi$ to $Q_{1}\cup Q_{2}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$. We color $Q_{3}$
correspondingly to how $Q_{2}$ is colored, and every edge between $Q_{2}$ and
$Q_{3}$ by the color in $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ missing
at its endpoints. All other edges in $D_{1}$ are colored $c_{1},c_{2}$
alternately so that the coloring agrees with $\varphi$. Finally, we color all
hitherto uncolored planes using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ so that the resulting coloring
agrees with $\varphi$. In conclusion, $\varphi$ is extendable. ∎

######  Lemma 4.4.

If each dimension of $G$ contains precolored edges and there is a dimension
with exactly one precolored edge, the color of which does appear on edges in
other dimensions of $G$, then $\varphi$ is extendable.

###### Proof.

Let $D_{1}$ be a dimension containing only one precolored edge $e$, colored
$c_{1}$ say, and consider the subgraph $G-E(D_{1})$ consisting of $2k+1$
planes $Q_{1},\dots,Q_{2k+1}$. Since at least one color appears on at least
two edges, there are two colors $c_{2},c_{3}\in\\{1,\dots,2d+1\\}$ that do not
appear on any edge under $\varphi$.

Case 1. All precolored edges of $G-E(D_{1})$ are contained in one plane:

In this case, we may proceed as in Case 1 of Lemma 3.4, but use Lemma 2.2
instead of Lemma 2.1. We omit the details.

Case 2. All precolored edges of $G-E(D_{1})$ are contained in two planes:

Let $Q_{1}$ and $Q_{i}$ be the two planes containing the precolored edges
distinct from $e$.

Let us first consider the case when $e$ is not incident to $Q_{1}$ or $Q_{i}$.
Since each of $Q_{1}$ and $Q_{i}$ contains at most $2d-2$ precolored edges,
there are extensions $f_{1}$ and $f_{i}$ of the restrictions of $\varphi$ to
$Q_{1}$ and $Q_{i}$, respectively, using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. Therafter we color the edges
of $D_{1}$ properly and correspondingly using colors $\\{c_{1},c_{2},c_{3}\\}$
so that the coloring agrees with the restriction of $\varphi$ to $D_{1}$ and
has no conflicts with $f_{1}$ or $f_{i}$. Finally we color the remaining
planes of $G-E(D_{1})$, as to obtain an extension of $\varphi$.

Suppose now that $e$ is incident with $Q_{1}$ and $Q_{2}$, and $i\neq 2$. Then
either $Q_{3}$ or $Q_{2k+1}$ contains no precolored edges; suppose $Q_{3}$.
(The case when $Q_{2k+1}$ has this property is similar.) As in the preceding
paragraph, there are extensions $f_{1}$ and $f_{i}$ of the restrictions of
$\varphi$ to $Q_{1}$ and $Q_{i}$, respectively, using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. We color $Q_{2}$ and $Q_{3}$
correspondingly to how $Q_{1}$ is colored. Next, we color every edge of
$D_{1}$ between $Q_{2}$ and $Q_{3}$ by a color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$ missing at its endpoints, and
then color all other edges of $D_{1}$ alternately by colors $c_{2}$ and
$c_{3}$ so that all edges between $Q_{1}$ and $Q_{2}$ are colored $c_{2}$. The
remaining uncolored planes of $G$ are properly colored using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. Now, if $e$ is adjacent to
edges colored $c_{1}$, then we swap colors on a bicolored $4$-cycle containing
$e$ and two edges colored $c_{1}$ to obtain an extension of $\varphi$;
otherwise we simply recolor $e$ to obtain an extension of $\varphi$.

Suppose now that $e$ is incident with $Q_{1}$ and $Q_{2}$, and $i=2$. By
removing the color from any edge that is colored $c_{1}$ under $\varphi$, we
obtain a precoloring $\varphi^{\prime}$ of $G$. The restriction of
$\varphi^{\prime}$ to $Q_{1}$ and $Q_{2}$ are extendable to proper edge
colorings, respectively, using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$. By recoloring any edge of
$Q_{1}$ and $Q_{2}$ that is $\varphi$-colored $c_{1}$ by the color $c_{1}$ we
obtain edge colorings $f_{1}$ of $Q_{1}$ and $f_{2}$ of $Q_{2}$, respectively.

Next, we color every edge between $Q_{1}$ and $Q_{2}$ by the color $c_{2}$
except that $e$ is colored $c_{1}$. Thereafter, we color $Q_{3},\dots,Q_{2k}$
correspondingly to how $Q_{2}$ is colored, and $Q_{2k+1}$ correspondingly to
how $Q_{1}$ is colored. Now, for every vertex $x$ of $Q_{2}$, there are colors
$c_{x},c^{\prime}_{x}\in\\{1,\dots,2d+1\\}$ that do not appear at $x$ in
$Q_{2}$ or on the incident edge between $Q_{1}$ and $Q_{2}$. We color every
path in $D_{1}$ from $Q_{2}$ to $Q_{2k}$ by colors $c_{x}$ and
$c^{\prime}_{x}$ alternately, and thereafter color every edge between $Q_{2k}$
and $Q_{2k+1}$ by the color of the edge in the same pillar between $Q_{1}$ and
$Q_{2}$. Finally, we color the edges between $Q_{1}$ and $Q_{2k+1}$ by a color
missing at its endpoints to obtain an extension of $\varphi$.

Case 3. All precolored edges of $G-E(D_{1})$ are contained in at least three
planes:

The assumption implies that every plane in $G-E(D_{1})$ contains at most
$2d-3$ precolored edges. Assume that $e$ is incident with $Q_{1}$ and $Q_{2}$.

Suppose first that $Q_{1}\cup Q_{2}$ contains altogether at most $2d-3$
precolored edges. Then there are uncolored corresponding edges $e_{1}\in
E(Q_{1})$ and $e_{2}\in E(Q_{2})$ that are adjacent to $e$ but not to any edge
in $Q_{1}\cup Q_{2}$ $\varphi$-colored $c_{1}$. From the restriction of
$\varphi$ to $G-E(D_{1})$ we define a new precoloring $\varphi^{\prime}$ by
coloring $e_{1}$ and $e_{2}$ by the color $c_{1}$. Thereafter we may proceed
as in Case 3 of the proof of Lemma 4.2 to obtain a proper $(2d+1)$-edge
coloring of $G$ which is an extension of $\varphi^{\prime}$ and where the
edges of $D_{1}$ are colored correspondingly. Thus, by swapping colors on a
bicolored $4$-cycle we obtain an extension of $\varphi$.

Suppose now that $Q_{1}\cup Q_{2}$ contains altogether $2d-2$ precolored
edges. If there are uncolored corresponding edges $e_{1}\in E(Q_{1})$ and
$e_{2}\in E(Q_{2})$ that are adjacent to $e$ but not to any edge in $Q_{1}\cup
Q_{2}$ $\varphi$-colored $c_{1}$, then we proceed as in the preceding
paragraph. So assume that there are no such edges $e_{1}$ and $e_{2}$. Then
there are $2d-2$ edges $e_{1},\dots,e_{2d-2}$ in $Q_{1}$ that are adjacent to
$e$ and such that each of these edges satisfies that

  * (i)

$e_{j}$ or the corresponding edge of $Q_{2}$ is precolored by a color distinct
from $c_{1}$, or

  * (ii)

$e_{j}$ or the corresponding edge of $Q_{2}$ is adjacent to an edge precolored
$c_{1}$.

Moreover, since $Q_{1}\cup Q_{2}$ is triangle-free and contains at most $2d-2$
precolored edges, every precolored edge in $Q_{1}\cup Q_{2}$ satisfies one of
these conditions. Now, for $j=1,2$, from the restriction of $\varphi$ to
$Q_{j}$, we define a new precoloring $\varphi_{j}$ of $Q_{j}$ by coloring
every edge of $Q_{1}$ and $Q_{2}$ that is adjacent to $e$ and does not satisfy
(i) or (ii) by a color in $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2},c_{3}\\}$
so that the resulting coloring is proper and agrees with $\varphi$. Now, by
the induction hypothesis, $\varphi_{j}$ is extendable to a proper edge
coloring of $Q_{j}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. Note that no edge of $Q_{1}$
or $Q_{2}$ adjacent to $e$ is colored $c_{1}$ in these colorings. Thus we may
color all edges between $Q_{1}$ and $Q_{2}$ by $c_{2}$ except $e$ which is
colored $c_{1}$.

Next, suppose that $Q_{r}$, $r\notin\\{1,2\\}$, is the third plane containing
a precolored edge. Then $Q_{r+1}$ or $Q_{r-1}$ contains no precolored or
hitherto colored edges, suppose $Q_{r+1}$. We take an extension of the
restriction of $\varphi$ to $Q_{r}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$, and color all other uncolored
planes correspondingly to how $Q_{r}$ is colored. Thereafter we color the
edges between $Q_{r}$ and $Q_{r+1}$ by the unique color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$ missing at it endpoints.
Finally, we color all remaining uncolored edges of $D_{1}$ by colors
$c_{2},c_{3}$ alternately so that the resulting coloring is proper. This
yields an extension of $\varphi$. ∎

######  Lemma 4.5.

If each dimension of $G$ contains exactly two precolored edges, at least one
of which is colored by a color appearing on precolored edges in other
dimensions, then $\varphi$ is extendable.

###### Proof.

Let $D_{1}$ be a dimension containing two precolored edges $e_{1}$ and
$e_{2}$. By assumption, at most $2d-1$ colors appear on edges under $\varphi$,
so let let $c_{3},c_{4}$ be two colors from $\\{1,\dots,2d+1\\}$ that do not
appear on any edges under $\varphi$.

Case 1. All precolored edges of $G-E(D_{1})$ are contained in one plane:

Suppose that all precolored edges except $e_{1}$ and $e_{2}$ lie in one
component $Q_{1}$ of $G-E(D_{1})$. Without loss of generality, we assume that
$\\{\varphi(e_{1}),\varphi(e_{2})\\}\subseteq\\{c_{1},c_{2}\\}$. We define a
new precoloring $\varphi^{\prime}$ from the restriction of $\varphi$ to
$Q_{1}$ by removing the colors $c_{1}$ and $c_{2}$ from any edges of $Q_{1}$
colored by these colors. Now, by the induction hypothesis $\varphi^{\prime}$
is extendable to a proper $(2d-1)$-edge coloring of $Q_{1}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$. By recoloring the edges of
$Q_{1}$ that are $\varphi$-colored $c_{1}$ and $c_{2}$ by colors $c_{1}$ and
$c_{2}$, respectively, we obtain a proper edge coloring $f^{\prime}$ of
$Q_{1}$. Next, we color all other planes of $G-E(D_{1})$ correspondingly and
define a list assignment for the edges of $D_{1}$ by assigning every edge the
set of colors from $\\{1,\dots,2d+1\\}$ not appearing on its adjacent edges.
Then each edge of $D_{1}$ receives a list of $3$ colors except for the two
edges $e_{1}$ and $e_{2}$ that are precolored. Thus, there is an extension of
$\varphi$.

Case 2. All precolored edges of $G-E(D_{1})$ are contained in two planes:

We shall consider several different subcases.

Case 2.1. The precolored edges of $D_{1}$ have the same color under $\varphi$:

Suppose that $\varphi(e_{1})=\varphi(e_{2})=c_{1}$. If $e_{1}$ and $e_{2}$ are
both incident with the same two planes, then we may apply arguments which are
similar to the ones in Case 2 of the proof of Lemma 4.4. Consequently, assume
that $e_{1}$ and $e_{2}$ are incident with at most one common plane.

Subcase 2.1.1. $e_{1}$ and $e_{2}$ are both incident with exactly one common
plane:

Suppose that $e_{1}$ and $e_{2}$ are both incident with the common plane
$Q_{1}$, and that $e_{1}$ is also incident with $Q_{2}$. If $Q_{1}$ and
$Q_{2}$ contain all precolored edges of $G-E(D_{1})$, then a similar argument
as in the subcase of Case 2 of Lemma 4.4 when $Q_{1}\cup Q_{2}$ contains all
precolored edges of $G-E(D_{1})$ again applies, so we omit the details here as
well.

It remains to consider the following subcases:

  * (a)

$Q_{1}$ contains precolored edges, but neither of $Q_{2}$ and $Q_{2k+1}$.

  * (b)

Either $Q_{2k+1}$ or $Q_{2}$, but not $Q_{1}$, contains precolored edges.

  * (c)

Both $Q_{2}$ and $Q_{2k+1}$ contain precolored edges.

(a) holds:

Suppose that $Q_{1}$ and $Q_{i}$ contains all precolored edges of
$G-E(D_{1})$, where $i\notin\\{1,2,3,2k+1\\}$. If $e_{1}$ and $e_{2}$ are
adjacent via an uncolored edge $e$ in $Q_{1}$, then since $Q_{1}$ contains at
most $2d-3$ precolored edges, there is a color
$c\in\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3},c_{4}\\}$ so that the
precoloring obtained from $\varphi$ by in addition coloring $e$ by the color
$c$ is proper. Denote the obtained coloring by $\varphi^{\prime}$. On the
other hand, if there is no such edge, then we set $\varphi^{\prime}=\varphi$.

Now, since both $Q_{1}$ and $Q_{i}$ contains at most $2d-2$
$\varphi^{\prime}$-precolored edges, there are extensions $f_{1}$ and $f_{i}$,
respectively, of the restrictions of $\varphi^{\prime}$ to $Q_{1}$ and
$Q_{i}$, respectively, using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$. We color
$Q_{2},Q_{3},Q_{2k+1}$ correspondingly to how $Q_{1}$ is colored, and
thereafter color every edge between $Q_{2}$ and $Q_{3}$ by the color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ missing at its endpoints.

Next, we color all hitherto uncolored edges of $D_{1}$ alternately using
colors $c_{3},c_{4}$ so that all edges between $Q_{1}$ and $Q_{2}$ have color
$c_{3}$, and also color all hitherto uncolored planes properly using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$. The obtained coloring is
proper and agrees with $\varphi^{\prime}$ except for $e_{1}$ and $e_{2}$. Now,
if neither $e_{1}$ of $e_{2}$ are adjacent to an edge colored $c_{1}$, then we
simply recolor them; otherwise, we swap on one or two bicolored cycles to
obtain an extension of $\varphi$; note that if both $e_{1}$ and $e_{2}$ are
adjacent to edges colored $c_{1}$, then these cycles are disjoint. Hence,
$\varphi$ is extendable.

(b) holds:

If instead either $Q_{2k+1}$ or $Q_{2}$, but not $Q_{1}$, contains precolored
edges, then a similar argument as in (a) applies, so we omit the details.

(c) holds:

Assume that $Q_{2}$ and $Q_{2k+1}$ contain all precolored edges of
$G-E(D_{1})$, and let $u_{2k+1}$ and $u_{2}$ be the vertices of $Q_{2k+1}$ and
$Q_{2}$ that are incident with $e_{1}$ and $e_{2}$, respectively.

If both $Q_{2k+1}$ and $Q_{2}$ contains at most $2d-4$ precolored edges, then
there are uncolored edges $e^{\prime}_{2k+1}\in E(Q_{2k+1})$ and
$e^{\prime}_{2}\in E(Q_{2})$ that are incident with $u_{2k+1}$ and $u_{2}$,
respectively, not adjacent to any edges of $Q_{2k+1}\cup Q_{2}$ precolored
$c_{1}$, and such that the corresponding edges of $Q_{1}$ are independent. We
color $e^{\prime}_{2k+1}$, $e^{\prime}_{2}$, and also the corresponding edges
of $Q_{1}$ by the color $c_{1}$. Together with $\varphi$, this defines a
precoloring of $Q_{2k+1}\cup Q_{1}\cup Q_{2}$, which by the induction
hypothesis is extendable to a proper edge coloring using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$. We color all edges between
$Q_{1}$ and $Q_{2}$ with color $c_{4}$, and all edges between $Q_{2k+1}$ and
$Q_{1}$ by the color $c_{3}$. Next, we color $Q_{2k}$ and $Q_{3}$
correspondingly to how $Q_{2k+1}$ and $Q_{2}$ are colored, respectively.
Thereafter we color all edges between $Q_{2k+1}$ and $Q_{2k}$ by the color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ missing at its endpoints, and
similarly for $Q_{2}$ and $Q_{3}$. Finally, we color all uncolored edges of
$D_{1}$ alternately by colors $c_{3},c_{4}$, color all hitherto uncolored
planes using colors $\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ and swap on
two bicolored cycles containing $e_{1}$ and $e_{2}$, respectively, to obtain
an extension of $\varphi$.

Suppose now instead that one of $Q_{2k+1}$ and $Q_{2}$ contains $2d-3$
precolored edges, say $Q_{2k+1}$. Then $Q_{2}$ contains exactly one precolored
edge $e$. By removing the color from any edge of $Q_{2k+1}$ that is precolored
$c_{1}$, we obtain a precoloring $\varphi^{\prime}$ from the restriction of
$\varphi$ to $Q_{2k+1}$. $\varphi^{\prime}$ is extendable to a proper coloring
of $Q_{2k+1}$ using colors $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3}\\}$ and
by recoloring the edges of $Q_{2k+1}$ $\varphi$-colored $c_{1}$ by the color
$c_{1}$ we obtain an extension $f_{2k+1}$ of the restriction of $\varphi$ to
$Q_{2k+1}$.

Next, we color $Q_{1}$ correspondingly to $Q_{2k+1}$ except that we color any
edge of $Q_{1}$ corresponding to an edge colored $c_{1}$ by the color $c_{3}$.
We color the edges between $Q_{2k+1}$ and $Q_{1}$ by an arbitrary color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3}\\}$ not appearing at its endpoints,
except that $e_{2}$ is colored $c_{1}$.

Suppose first that $e$ is precolored $c_{1}$. Then we color $Q_{2}$
correspondingly to how $Q_{1}$ is colored, but color $e$ by color $c_{1}$.
Next we color all edges between $Q_{1}$ and $Q_{2}$ by an arbitrary color in
$\\{1,\dots,2d+1\\}$ missing at its endpoints except that $e_{1}$ is colored
$c_{1}$. Thereafter, we color $Q_{3}$ correspondingly to how $Q_{1}$ is
colored, and all remaining uncolored planes correspondingly to how $Q_{2k+1}$
is colored. We may then color the hitherto uncolored edges of $D_{1}$
appropriately to obtain an extension of $\varphi$.

Suppose now that the precolored edge of $Q_{2}$ is colored $c_{2}\neq c_{1}$.
Let $e^{\prime}$ be the edge of $Q_{1}$ corresponding to $e$, and assume that
$e^{\prime}$ is colored $c^{\prime}$ in the hiherto constructed coloring. We
color $Q_{2}$ correspondingly to how $Q_{1}$ is colored but permute the colors
$c_{2}$ and $c^{\prime}$ in the coloring of $Q_{2}$. Thereafter, we color
$Q_{3}$ correspondingly to $Q_{2}$ except that we permute colors $c_{2}$ and
$c^{\prime}$, and finally we color the remaining uncolored edges of $G$ by
proceeding as in the preceding paragraph.

Subcase 2.1.2 $e_{1}$ and $e_{2}$ are not incident with a common plane:

Suppose that $e_{1}$ is incident with $Q_{1}$ and $Q_{2}$ and $e_{2}$ is
incident with $Q_{j}$ and $Q_{j+1}$, and all these four planes are distinct.
If all precolored edges are contained in $Q_{1}\cup Q_{2}$, then as before we
may then select corresponding uncolored edges $e^{\prime}_{j}$ and
$e^{\prime}_{j+1}$ of $Q_{j}$ and $Q_{j+1}$ that are adjacent to $e_{2}$.
Next, we consider the precoloring $\varphi^{\prime}$ obtained from $\varphi$
by coloring $e^{\prime}_{j}$ and $e^{\prime}_{j+1}$ by $c_{1}$ and removing
the color $c_{1}$ from $e_{2}$. We may now apply similar arguments as in the
subcase of Case 3 of Lemma 4.4 when $Q_{1}\cup Q_{2}$ contains $2d-2$
precolored edges to obtain an extension of $\varphi^{\prime}$. In particular,
since there is at least one plane in $G$ that is distinct from
$Q_{1},Q_{2},Q_{j},Q_{j+1}$ that contains no $\varphi^{\prime}$-colored edges,
we can color the edges of $D_{1}$ so that all edges between $Q_{j}$ and
$Q_{j+1}$ have the same color. We may then swap on a bicolored $4$-cycle to
obtain an extension of $\varphi$.

Suppose now that exactly one of the planes $Q_{1}$ and $Q_{2}$, and exactly
one of the planes $Q_{j}$ and $Q_{j+1}$ contain precolored edges. Assume e.g.
that $Q_{1}$ and $Q_{j}$ contains no precolored edges (the other cases are
analogous). We pick an edge $e^{\prime}_{2}$ in $Q_{2}$ that is uncolored and
adjacent to $e_{1}$ but not adjacent to any other edge precolored $c_{1}$, and
a similar edge $e^{\prime}_{j+1}$ of $Q_{j+1}$; since each of these planes
contains at most $2d-3$ precolored edges, such edges exist. From the
restriction of $\varphi$ to $Q_{2}\cup Q_{j+1}$ we define a new precoloring
$\varphi^{\prime}$ by in addition coloring $e^{\prime}_{2}$ and
$e^{\prime}_{j+1}$ $c_{1}$. Now, by the induction hypothesis, there are
extensions $f_{2}$ and $f_{j+1}$ of the restrictions of $\varphi^{\prime}$ to
$Q_{2}$ and $Q_{j+1}$, respectively, using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$.

Let us now color the other planes of $G-E(D_{1})$. Without loss of generality,
we assume that $j+1<2k+1$. We color $Q_{1}$ and $Q_{2k+1}$ correspondingly to
how $Q_{2}$ is colored, $Q_{j}$ correspondingly to how $Q_{j+1}$ is colored,
and all other planes arbitrarily using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$. Thereafter we color all edges
between $Q_{1}$ and $Q_{2k+1}$ by a color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ missing at its endpoints, and
all other edges of $D_{1}$ alternately using colors $c_{3},c_{4}$ and starting
with color $c_{3}$ at $Q_{1}$. Finally, we swap colors on two bicolored
$4$-cycles containing $e_{1}$ and $e_{2}$, respectively, to obtain an
extension of $\varphi$.

Finally, we consider the case when $Q_{1}$ may contain precolored edges, but
none of $Q_{2},Q_{j},Q_{j+1}$ contains precolored edges. We define a
precoloring $\varphi^{\prime}$ from the restriction of $\varphi$ to $Q_{1}$ by
selecting an edge $e^{\prime}_{1}\in E(Q_{1})$ adjacent to $e_{1}$ and
coloring it $c_{1}$, as before. Thereafter, we take an extension of
$\varphi^{\prime}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$, and color $Q_{2}$
correspondingly. Next, we color all edges between $Q_{j}$ and $Q_{j+1}$ by the
color $c_{1}$, and all other edges of $D_{1}$ alternately using colors $c_{3}$
and $c_{4}$, and starting with color $c_{3}$ at $Q_{j+1}$. We now obtain an
extension of $\varphi$ as before.

Case 2.2 The precolored edges of $D_{1}$ are colored differently under
$\varphi$:

Suppose that $\varphi(e_{1})=c_{1}$ and $\varphi(e_{2})=c_{2}$. We shall
consider some different cases.

Subcase 2.2.1 $e_{1}$ and $e_{2}$ are both incident with two common planes:

Suppose that $e_{1}$ and $e_{2}$ are both incident with the planes $Q_{1}$ and
$Q_{2}$. Let $u_{1}$ and $u_{2}$ be the vertices in $Q_{1}$ that are incident
with $e_{1}$ and $e_{2}$, respectively.

If none of $Q_{1}$ and $Q_{2}$ contains precolored edges, then we can select
independent edges in $Q_{1}$ (and $Q_{2}$) that are incident with $u_{1}$ and
$u_{2}$, respectively, and color them $c_{1}$ and $c_{2}$. Then we may proceed
as in Case 3 of Lemma 4.2 to obtain an extension of the resulting precoloring
$\varphi^{\prime}$ of $G-E(D_{1})$, and thereafter we obtain an extension of
$\varphi$, as before.

Let us now assume that all precolored edges are contained in $Q_{1}\cup
Q_{2}$. We first prove the following claim.

######  Claim 4.6.

Suppose $d\geq 3$. At least one of the following two statements hold.

(i) There is an edge $e^{\prime}_{1}\in E(Q_{1})$ incident with $u_{1}$ but
not $u_{2}$, such that $e^{\prime}_{1}$ and the corresponding edge
$e^{\prime\prime}_{1}$ of $Q_{2}$ are uncolored and not adjacent to any edge
colored $c_{1}$.

(ii) There is an edge $e^{\prime}_{2}\in E(Q_{1})$ incident with $u_{2}$ but
not $u_{1}$, such that $e^{\prime}_{2}$ and the corresponding edge
$e^{\prime\prime}_{2}$ of $Q_{2}$ are uncolored and not adjacent to any edge
colored $c_{2}$.

###### Proof.

Suppose that (i) is false. Since $G-E(D_{1})$ is triangle-free and
$(2d-2)$-regular, there are $2d-3$ edges $a_{1},\dots,a_{2d-3}\in E(Q_{1})$
incident with $u_{1}$, all of which are either precolored, adjacent to an edge
colored $c_{1}$, or satisfies that the corresponding edge of $Q_{2}$ satisfies
one of these conditions. Since $Q_{1}\cup Q_{2}$ contains $2d-2$ precolored
edges, it is easy to see that then (ii) must hold, so there is an edge
$e^{\prime}_{2}$ as desired. ∎

If $d=2$, we note that the claim might fail if $u_{1}$ and $u_{2}$ are
adjacent via an uncolored edge. However, in this case, it is trivial to verify
that $\varphi$ is extendable, since every precoloring of an odd cycle is
extendable using $3$ colors.

Suppose now that (ii) of Claim 4.6 holds, and let $e^{\prime}_{2}$ and
$e^{\prime\prime}_{2}$ be corresponding edges of $Q_{1}$ and $Q_{2}$
respectively, as described in the claim. From the restriction of $\varphi$ to
$Q_{1}\cup Q_{2}$ we define a new precoloring $\varphi^{\prime}$ of $Q_{1}\cup
Q_{2}$ by in addition coloring $e^{\prime}_{2}$ and $e^{\prime\prime}_{2}$ by
the color $c_{2}$. We may now proceed as in the subcase of Case 2 of the proof
of Lemma 4.4 when all the precolored edges are contained in $Q_{1}\cup Q_{2}$,
to obtain an extension of $\varphi^{\prime}$ (with $c_{3}$ in place of
$c_{2}$). Thereafter, we swap colors on a bicolored $4$-cycle containing
$e_{2}$ to obtain an extension of $\varphi$.

It remains to consider the case when all precolored edges are contained in
$Q_{1}$ and $Q_{i}$, where $i\neq 2$. Then either $Q_{3}$ or $Q_{2k+1}$
contains no precolored edges, say $Q_{3}$.

Suppose first that $Q_{1}$ contains at most $2d-4$ precolored edges. Then
since $Q_{1}$ is $(2r-2)$-regular, there are independent uncolored edges
$e^{\prime}_{1}\in E(Q_{1})$ and $e^{\prime}_{2}\in E(Q_{1})$ incident with
$u_{1}$ and $u_{2}$, respectively, and such that $e^{\prime}_{1}$ is not
adjacent to any edge of $Q_{1}$ $\varphi$-colored $c_{1}$, and
$e^{\prime}_{2}$ is not adjacent to any edge of $Q_{1}$ $\varphi$-colored
$c_{2}$.

From the restriction of $\varphi$ to $Q_{1}$ we define a new precoloring
$\varphi^{\prime}$ of $Q_{1}$ by in addition coloring $e^{\prime}_{1}$ by the
color $c_{1}$, and $e^{\prime}_{2}$ by the color $c_{2}$. Next, we take an
extension of $\varphi^{\prime}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$, and color $Q_{2}$ and $Q_{3}$
correspondingly to how $Q_{1}$ is colored. Thereafter, we color the edges of
$D_{1}$ as follows: color all edges between $Q_{2}$ and $Q_{3}$ by a color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ missing at its endpoints, and
color all other edges of $D_{1}$ alternately using colors $c_{3}$ and $c_{4}$
so that all edges between $Q_{1}$ and $Q_{2}$ are colored $c_{3}$. Thereafter,
we color the planes $Q_{4},\dots,Q_{2k+1}$ with colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ so that the coloring agrees
with $\varphi$. Now we may obtain an extension of $\varphi$ by swapping colors
on two bicolored $4$-cycles containing $e_{1}$ and $e_{2}$, respectively.

Suppose now that $Q_{1}$ contains exactly $2d-3$ precolored edges. Then
$Q_{i}$ contains exactly one precolored edge. Moreover, as in the proof of
Claim 4.6 it is straightforward that there is

  * •

either an edge $e^{\prime}_{1}$ satisfying (i) of Claim 4.6, or

  * •

an edge $e^{\prime}_{2}$ satisfying (ii) of Claim 4.6.

Suppose e.g. that (i) holds. Then from the restriction of $\varphi$ to $Q_{1}$
we define a new precoloring $\varphi^{\prime}$ of $Q_{1}$ by in addition
coloring $e^{\prime}_{1}$ by the color $c_{1}$ and removing the color from any
edge of $Q_{1}$ that is colored $c_{2}$.

Next, we take an extension of $\varphi^{\prime}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$, recolor the edges
$\varphi$-colored $c_{2}$ by the color $c_{2}$, and thereafter color $Q_{2}$
and $Q_{3}$ correspondingly to how $Q_{1}$ is colored. Denote the obtained
coloring by $f$. We color all edges between $Q_{1}$ and $Q_{2}$ by the color
$c_{3}$ except $e_{2}$ which is colored $c_{2}$, and color the edges between
$Q_{2}$ and $Q_{3}$ by a color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$ missing at its endpoints.

Now, let $e^{\prime\prime}_{i}$ be the edge of $Q_{i}$ that is precolored, and
let $e^{\prime\prime}_{1}$ be the corresponding edge of $Q_{1}$. If
$f(e^{\prime\prime}_{1})=\varphi(e^{\prime\prime}_{i})$, then we color all
hitherto uncolored planes correspondingly to how $Q_{1}$ is colored, therafter
color the remaining uncolored edges of $D_{1}$ and finally swap colors on a
bicolored $4$-cycle containing $e_{1}$ to obtain an extension of $\varphi$.

Otherwise, if $f(e^{\prime\prime}_{1})\neq\varphi(e^{\prime\prime}_{i})$, then
we color all other planes correspondingly to how $Q_{1}$ is colored, except
that we permute the colors $f(e^{\prime\prime}_{1})$ and
$\varphi(e^{\prime\prime}_{i})$ in the colorings. We may now apply similar
arguments as before to obtain an extension of $\varphi$; we leave the details
to the reader.

Subcase 2.2.2 $e_{1}$ and $e_{2}$ are incident with exactly one common plane:

Suppose that $e_{1}$ is incident with $Q_{1}$ and $Q_{2}$, and $e_{2}$ with
$Q_{1}$ and $Q_{2k+1}$. Let $u_{1}$ and $u_{2}$ be the vertices of $Q_{1}$
that are incident with $e_{1}$ and $e_{2}$, respectively. If neither of
$Q_{1},Q_{2},Q_{2k+1}$ contains precolored edges, then a similar argument as
in the second paragraph of Subcase 2.2.1 applies. Thus it suffices to consider
the following subcases:

  * (a)

All precolored edges of $G-E(D_{1})$ are contained in $Q_{1}\cup Q_{2}$.

  * (b)

$Q_{1}$ contains precolored edges, but neither of $Q_{2}$ and $Q_{2k+1}$.

  * (c)

$Q_{2}$, but not $Q_{1}$ or $Q_{2k+1}$, contains precolored edges.

  * (d)

All precolored edges of $G-E(D_{1})$ are contained in $Q_{2}\cup Q_{2k+1}$.

By symmetry, it suffices to consider these cases.

(a) holds:

We first consider the case when there is an edge $e^{\prime}_{1}\in E(Q_{1})$
adjacent to $e_{1}$, such that both $e^{\prime}_{1}$ and the corresponding
edge $e^{\prime}_{2}\in E(Q_{2})$ are uncolored and not adjacent to any edge
precolored $c_{1}$. If this holds, then from the restriction of $\varphi$ to
$Q_{1}\cup Q_{2}$ we define a new precoloring $\varphi^{\prime}$ by coloring
$e^{\prime}_{1}$ and $e^{\prime}_{2}$ by the color $c_{1}$, and also removing
the color from any edge that is $\varphi$-colored $c_{2}$.

By the induction hypothesis, there is an extension of $\varphi^{\prime}$ using
colors $\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. By recoloring the edges
of $Q_{1}$ and $Q_{2}$ that are $\varphi$-colored $c_{2}$ by the color $c_{2}$
we obtain an edge coloring $f$ of $Q_{1}\cup Q_{2}$. We color all edges
between $Q_{1}$ and $Q_{2}$ by the color $c_{3}$, all the planes
$Q_{3},\dots,Q_{2k}$ correspondingly to how $Q_{2}$ is colored, and $Q_{2k+1}$
correspondingly to how $Q_{1}$ is colored. Now the edges between $Q_{2k+1}$
and $Q_{2k}$ can be colored with the color $c_{3}$, and every other edge of
$D_{1}$ by some appropriate color missing at its endpoints. Thus by swapping
colors on a bicolored $4$-cycle containing $e_{1}$ we obtain an extension of
$\varphi$.

Suppose now that there is no edge $e^{\prime}_{1}\in E(Q_{1})$ adjacent to
$e_{1}$, such that both $e^{\prime}_{1}$ and the corresponding edge
$e^{\prime}_{2}\in E(Q_{2})$ are uncolored and not adjacent to any edge
precolored $c_{1}$. Then, since $Q_{1}\cup Q_{2}$ is $(2d-2)$-regular and
contains $2d-2$ precolored edges, $u_{1}$ is incident with $2d-2$ edges
$a_{1},\dots,a_{2d-2}$ such that each $a_{i}$, or the corresponding edge of
$Q_{2}$, is $\varphi$-colored by a color distinct from $c_{1}$, or uncolored
and adjacent to an edge $\varphi$-colored $c_{1}$. In particular, if there is
an edge of $Q_{1}\cup Q_{2}$ colored $c_{2}$, then at most one edge in each of
$Q_{1}$ and $Q_{2}$ is colored $c_{2}$. Moreover, since $G$ is triangle-free
and $Q_{1}\cup Q_{2}$ contains exactly $2d-2$ precolored edges, an edge in
$Q_{1}\cup Q_{2}$ precolored $c_{2}$ is not adjacent to an edge precolored
$c_{1}$ in $Q_{1}\cup Q_{2}$.

If $Q_{1}$ contains an edge $a$ precolored $c_{2}$, then from the restriction
of $\varphi$ to $Q_{1}\cup Q_{2}$, we define a precoloring $\varphi^{\prime}$
by recoloring $a$ and also the corresponding edge of $Q_{2}$ by the color
$c_{1}$. Otherwise, if both $Q_{1}$ and $Q_{2}$ contain edges precolored
$c_{2}$, then we define $\varphi^{\prime}$ by recoloring these edges by the
color $c_{1}$. Now, by the induction hypothesis, there is an extension of the
coloring $\varphi^{\prime}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. By recoloring the edges that
were recolored $c_{1}$ by the color $c_{2}$ we obtain an extension of the
restriction of $\varphi$ to $Q_{1}\cup Q_{2}$. Next, we color $e_{1}$ by the
color $c_{1}$ and all other edges between $Q_{1}$ and $Q_{2}$ by the color
$c_{3}$. We color $Q_{2k+1}$ correspondingly to $Q_{1}$, and
$Q_{3},\dots,Q_{2k}$ correspondingly to how $Q_{2}$ is colored, and then color
the hitherto uncolored edges of $D_{1}$ as before to obtain an extension of
$\varphi$.

On the other hand, if no edge of $Q_{1}$ is colored $c_{2}$, then from the
restriction of $\varphi$ to $Q_{1}\cup Q_{2}$, we define a new precoloring
$\varphi^{\prime}$ by coloring all edges adjacent to $e_{1}$ that are not
precolored or adjacent to an edge colored $c_{1}$ in $G-E(D_{1})$ by an
arbitrary color from $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2},c_{3}\\}$ so
that the resulting precoloring is proper. By the induction hypothesis, the
obtained precoloring of $Q_{1}$ is extendable to a proper coloring using
colors $\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$, and the precoloring of
$Q_{2}$ is extendable using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$, where $c_{4}$ is some
arbitrary color not appearing on an edge of $Q_{2}$. Note that no edge
adjacent to $e_{1}$ is colored $c_{1}$ in this coloring. Hence, we can color
$Q_{2k+1}$ correspondingly to how $Q_{1}$ is colored, all edges between
$Q_{1}$ and $Q_{2k+1}$ by the color $c_{2}$, and all edges between $Q_{1}$ and
$Q_{2}$ by the color $c_{3}$ except that $e_{1}$ is colored $c_{1}$. Since not
other planes in $G-E(D_{1})$ contains precolored edges, it is now
straightforward to obtain an extension of $\varphi$ from this partial
coloring.

(b) holds:

Suppose that $Q_{1}$ and $Q_{i}$ contain all precolored edges of $G-E(D_{1})$,
where $i\notin\\{1,2,3,2k+1\\}$. We take an extension of the restriction of
$\varphi$ to $Q_{1}\cup Q_{i}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$, color $Q_{2},Q_{3},Q_{2k+1}$
correspondingly to how $Q_{1}$ is colored, and all remaning planes in
$G-E(D_{1})$ by the colors $\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ so
that the coloring agrees with $\varphi$. Next, we color the edges of $D_{1}$:
the edges between $Q_{2}$ and $Q_{3}$ we color with the color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ missing at its endpoints, and
all other edges of $D_{1}$ are colored $c_{3}$ and $c_{4}$ alternately, and
starting with color $c_{3}$ at $Q_{2}$. This yields a coloring that agrees
with $\varphi$ except for $e_{1}$ and $e_{2}$. We recolor these edges by
$c_{1}$ and $c_{2}$, respectively, possibly by swapping on one or two
bicolored $4$-cycles if necessary, to obtain an extension of $\varphi$.

(c) holds:

The case when $Q_{2}$, but not $Q_{2k+1}$ or $Q_{1}$, contains precolored
edges can be dealt with as in the preceding pagragraph, so we omit the details
here.

(d) holds:

If $d=2$, then it is straightforward that $\varphi$ is extendable, because any
partial $3$-edge coloring of an odd cycle is extendable. If $d>2$, then since
$Q_{2}\cup Q_{2k+1}$ contains exactly $2d-2$ precolored edges, it is
straightforward that there are non-corresponding edges $e^{\prime}_{2k+1}\in
E(Q_{2k+1})$ and $e^{\prime}_{2}\in E(Q_{2})$ that are uncolored, adjacent to
$e_{1}$ and $e_{2}$, respectively, and not adjacent to any edges of
$Q_{2k+1}\cup Q_{2}$ precolored $c_{2}$ and $c_{1}$, respectively.

From the restriction of $\varphi$ to $Q_{2k+1}\cup Q_{1}\cup Q_{2}$, we define
a new precoloring $\varphi^{\prime}$ of $Q_{2k+1}\cup Q_{1}\cup Q_{2}$ by in
addition coloring $e^{\prime}_{2k+1}$ by $c_{2}$, $e^{\prime}_{2}$ by the
color $c_{1}$, and the corresponding edges of $Q_{1}$ by colors $c_{2}$ and
$c_{1}$ respectively. By the induction hypothesis, there is an extension of
$\varphi^{\prime}$ to $Q_{2k+1}\cup Q_{1}\cup Q_{2}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$. From this coloring we may now
obtain an extension of $\varphi$ by proceeding as before.

Subcase 2.2.3 $e_{1}$ and $e_{2}$ are not incident with any common plane:

Suppose that $e_{1}$ is incident with $Q_{1}$ and $Q_{2}$, and $e_{2}$ is
incident with $Q_{j}$ and $Q_{j+1}$. As in Subcase 2.1.2, we can distinguish
between the following three cases:

  * •

All precolored edge are contained in $Q_{1}$ and $Q_{2}$.

  * •

One of $Q_{1}$ and $Q_{2}$, and one of $Q_{j}$ and $Q_{j+1}$, contain
precolored edges.

  * •

At most one of the planes $Q_{1},Q_{2},Q_{j},Q_{j+1}$ contains precolored
edges.

Moreover, in all these three subcases we may proceed precisely as in the
corresponding subcases of Subcase 2.1.2. We omit the details.

Case 3. All precolored edges of $G-E(D_{1})$ are contained in at least three
planes:

In the case when no precolored edge of $D_{1}$ is incident with a plane
containing precolored edges, then it is straightforward to obtain an extension
by selecting uncolored edges in the planes that the precolored edges of
$D_{1}$ are incident with, so throughout we assume that this is not the case.
Note further that since $G$ contains at least five precolored edges, $d\geq
3$.

Case 3.1. The precolored edges of $D_{1}$ have the same color under $\varphi$:

Suppose that $\varphi(e_{1})=\varphi(e_{2})=c_{1}$. We consider a number of
different subcases.

Subcase 3.1.1 $e_{1}$ and $e_{2}$ are incident with the same two planes:

Assume that $e_{1}$ and $e_{2}$ are incident with the same two planes $Q_{1}$
and $Q_{2}$. If the endpoints of $e_{1}$ and $e_{2}$ are adjacent via
uncolored edges in both $Q_{1}$ and $Q_{2}$, then we define the precoloring
$\varphi^{\prime}$ from the restriction of $\varphi$ to $Q_{1}\cup Q_{2}$ by
coloring these edges of $Q_{1}$ and $Q_{2}$ by the color $c_{1}$. We may now
proceed as in Case 3 of Lemma 4.2 to obtain an extension of
$\varphi^{\prime}$, and thereafter swap colors on a bicolored $4$-cycle to
obtain an extension of $\varphi$.

Otherwise, if the endpoints of $e_{1}$ and $e_{2}$ are not adjacent via
uncolored edges in both $Q_{1}$ and $Q_{2}$. Then, since $d>2$, $Q_{1}\cup
Q_{2}$ contains at most $2d-3$ precolored edges and any two vertices in $G$
are contained in at most one $5$-cycle, it is not hard to see that there are
independent edges $e^{\prime}_{1}$ and $e^{\prime}_{2}$ in $Q_{1}$, adjacent
to $e_{1}$ and $e_{2}$, respectively, and such that neither these edges, nor
the corresponding edges of $Q_{2}$ are precolored or adjacent to edges
precolored $c_{1}$ in $Q_{1}\cup Q_{2}$. Hence, we may color these edges of
$Q_{1}$ and $Q_{2}$ by the color $c_{1}$, and then proceed as in the preceding
paragraph to obtain an extension of $\varphi$.

Subcase 3.1.2 $e_{1}$ and $e_{2}$ are incident with one common plane:

Suppose that $e_{1}$ and $e_{2}$ are incident with exactly one common plane
$Q_{1}$, and that $e_{1}$ is also incident with $Q_{2}$. If there are at most
$2d-4$ precolored edges in $Q_{1}\cup Q_{2}$ and at most $2d-4$ precolored
edges in $Q_{2k+1}\cup Q_{1}$, then there are independent edges
$e^{\prime}_{1}$ and $e^{\prime}_{2}$ in $Q_{1}$, adjacent to $e_{1}$ and
$e_{2}$, respectively, and such that neither these edges, nor the
corresponding edges of $Q_{2}$ and $Q_{2k+1}$, respectively, are precolored or
adjacent to edges precolored $c_{1}$ in $Q_{1}\cup Q_{2}\cup Q_{2k+1}$. Thus
we may proceed as above to obtain an extension of $\varphi$.

Suppose now instead that $Q_{1}\cup Q_{2k+1}$, say, contains exactly $2d-3$
precolored edges. If there exist independent edges $e^{\prime}_{1}$ and
$e^{\prime}_{2}$ in $Q_{1}$, as described in the preceding paragraph, then we
may proceed as in that case, so suppose that there are no two such edges.

We first consider the case when we can choose exactly one such edge, that is,
there is an edge $e^{\prime}_{1}\in E(Q_{1})$ adjacent to $e_{1}$ but not
$e_{2}$, satisfying that $e^{\prime}_{1}$ and the corresponding edge of
$Q_{2}$ are not precolored or adjacent to edges of $Q_{1}\cup Q_{2}$ that are
precolored $c_{1}$. Moreover, there is no edge $e^{\prime}_{2}$ adjacent to
$e_{2}$ with analogous properties. Consider the precoloring $\varphi^{\prime}$
obtained from the restriction of $\varphi$ to $Q_{2k+1}\cup Q_{1}\cup Q_{2}$
by in addition coloring $e^{\prime}_{1}$ and also the corresponding edge of
$Q_{2}$ by the color $c_{1}$. Now, since there is no uncolored edge
$e^{\prime}_{2}$ as described above, it follows that all $d-2$ edges
$a_{1},\dots,a_{d-2}$ adjacent to $e_{2}$ in $Q_{1}$ satisfies that either
$a_{i}$, or the corresponding edge of $Q_{2k+1}$, is
$\varphi^{\prime}$-precolored or adjacent to an edge colored $c_{1}$ under
$\varphi^{\prime}$. Moreover, since $Q_{2k+1}\cup Q_{1}$ contains at most
$2d-2$ $\varphi^{\prime}$-precolored edges, every precolored edge of
$Q_{2k+1}\cup Q_{1}$ satisfies this condition. Thus by properly coloring the
uncolored edges adjacent to $e_{2}$, except the ones that are adjacent to
edges in $G-E(D_{1})$ colored $c_{1}$, by colors from
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3},c_{4}\\}$, we obtain a precoloring
$\varphi^{\prime\prime}$ from $\varphi^{\prime}$. Note that any extension of
the restriction of $\varphi^{\prime\prime}$ to $Q_{2k+1}\cup Q_{1}$ using
colors $\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$ does not use $c_{1}$ on
an edge adjacent to $e_{2}$. Thus, since there is exactly one precolored edge
in $G-E(D_{1})$ that is not contained in $Q_{2k+1}\cup Q_{1}$, we may once
again proceed as in Case 3 of Lemma 4.2 to obtain a proper $(2d+1)$-edge
coloring of $G$ that agrees with $\varphi^{\prime\prime}$, where no edge
adjacent to $e_{2}$ is colored $c_{1}$, and where we color the edges of
$D_{1}$ so that all edges between any two given planes are colored by a fixed
color not appearing in these two planes. Thereafter we can swap colors on a
bicolored $4$-cycle and recolor $e_{2}$ to obtain an extension of $\varphi$.

Suppose now that neither an edge $e^{\prime}_{1}$, nor an edge
$e^{\prime}_{2}$ as described above exist in $Q_{1}$. Then the endpoints
$u_{1}$ and $u_{2}$ of $e_{1}$ and $e_{2}$ in $Q_{1}$, respectively, are
adjacent via an uncolored edge $e$ in $Q_{1}$, and the corresponding edges of
$Q_{2k+1}$ and $Q_{2}$ are uncolored. Moreover, since both $Q_{2k+1}\cup
Q_{1}$ and $Q_{1}\cup Q_{2}$ contains at most $2d-3$ precolored edges, it
follows that there are $2d-4$ edges precolored $c_{1}$ in $Q_{1}$, the
endpoints of which are adjacent to $u_{1}$ and $u_{2}$, respectively.
Moreover, $Q_{2k+1}$ contains exactly one precolored edge, and $Q_{2}$
contains exactly one precolored edge, so all precolored edges of $G-E(D_{1})$
are contained in $Q_{2k+1}\cup Q_{1}\cup Q_{2}$.

Now, from the restriction of $\varphi$ to $Q_{2k+1}$ we define a new
precoloring $\varphi^{\prime}$ by coloring all edges of $Q_{2k+1}$
corresponding to edges of $Q_{1}$ colored $c_{1}$, by the color $c_{1}$, and
thereafter color every edge adjacent to $e_{2}$ in $Q_{2k+1}$ that is neither
precolored nor adjacent to any edge precolored $c_{1}$ by an arbitrary color
in $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3},c_{4}\\}$ so that the resulting
coloring is proper. Next, we take an extension of $\varphi^{\prime}$ using
colors $\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$. (Note that no edge
adjacent to $e_{2}$ is colored $c_{1}$ in this extension.) Thereafter we color
$Q_{1}$ correspondingly to how $Q_{2k+1}$ is colored except that all edges
colored $c_{1}$ that are not precolored $c_{1}$ under $\varphi^{\prime}$ are
recolored $c_{3}$. Denote the obtained partial coloring of $G$ by $f$.

Now, if the precolored edge $b_{2}$ of $Q_{2}$ is colored $c_{1}$, then we
color $Q_{2}$ correspondingly to how $Q_{1}$ is colored but recolor the edge
$\varphi$-precolored $c_{1}$ by the color $c_{1}$. Therafter, we color
$Q_{3},\dots,Q_{2k}$ correspondingly to how $Q_{1}$ is colored. We may now
apply Lemma 2.2 to color the edges of $D_{1}$ and thus obtain an extension of
$\varphi$. (Since $e_{1}$ and $e_{2}$ are contained in different cycles of
$D_{1}$, we can choose the coloring of $D_{1}$ so that it agrees with
$\varphi$.) Otherwise, if $b_{2}$ is colored $c_{5}\neq c_{1}$, then the
corresponding edge of $Q_{1}$ is not colored $c_{1}$. We color $Q_{2}$
correspondingly to how $Q_{1}$ is colored except that we permute the colors
$c_{5}$ and the color of the corresponding edge of $Q_{1}$ under $f$. Again,
we color all the planes $Q_{3},\dots,Q_{2k}$ correspondingly to how $Q_{1}$ is
colored, and apply Lemma 2.2 to obtain an extension of $\varphi$.

Subcase 3.1.3 $e_{1}$ and $e_{2}$ are not incident with any common plane:

Suppose that $e_{1}$ is incident with $Q_{1}$ and $Q_{2}$ and $e_{2}$ is
incident with $Q_{j}$ and $Q_{j+1}$, $j>2$. Since each $Q_{i}$ is
$(2d-2)$-regular and any pair of adjacent planes contains at most $2d-3$
precolored edges, it is straightforward that there are corresponding uncolored
edges $e^{\prime}_{1}\in E(Q_{1})$, $e^{\prime}_{2}\in E(Q_{2})$ adjacent to
$e_{1}$ but not to any other edge precolored $c_{1}$, and similarly for
$e_{2}$. Hence, we may proceed as in Case 3 of Lemma 4.2 to obtain an
extension of a precoloring $\varphi^{\prime}$ of $G-E(D_{1})$ defined from
$\varphi$ by coloring the selected edges adjacent to $e_{1}$ and $e_{2}$,
respectively, by the color $c_{1}$ and removing the color $c_{1}$ from $e_{1}$
and $e_{2}$. From the extension of $\varphi^{\prime}$, we obtain an extension
of $\varphi$ as before.

Case 3.2. The precolored edges of $D_{1}$ have different colors under
$\varphi$:

Suppose that $\varphi(e_{1})=c_{1}$ and $\varphi(e_{2})=c_{2}$.

Subcase 3.2.1 $e_{1}$ and $e_{2}$ are both incident with two common planes:

Assume that $e_{1}$ and $e_{2}$ are both incident with the same pair of planes
$Q_{1}$ and $Q_{2}$. Let $u_{1}$ and $u_{2}$ be the vertices of $Q_{1}$ that
are incident with $e_{1}$ and $e_{2}$, respectively.

If $Q_{1}\cup Q_{2}$ contains at most $2d-4$ precolored edges, then there are
independent edges $e^{\prime}_{1}\in E(Q_{1})$ and $e^{\prime}_{2}\in
E(Q_{1})$ that are incident with $u_{1}$ and $u_{2}$, respectively, such that
neither $e^{\prime}_{1}$ nor the corresponding edge $e^{\prime\prime}_{1}$ of
$Q_{2}$ is precolored or adjacent to an edge precolored $c_{1}$ in $Q_{1}\cup
Q_{2}$, and similarly for $e^{\prime}_{2}$, the corresponding edge
$e^{\prime\prime}_{2}$ of $Q_{2}$ and $c_{2}$. Thus, from the restriction of
$\varphi$ to $Q_{1}\cup Q_{2}$ we may define a new precoloring
$\varphi^{\prime}$ by coloring these four edges by $c_{1}$ and $c_{2}$,
respectively. We may now proceed as in Case 3 of Lemma 4.2 to obtain an
extension of $\varphi^{\prime}$, and thereafter we can obtain an extension of
$\varphi$ by swapping colors on two bicolored $4$-cycles.

Suppose now that $Q_{1}\cup Q_{2}$ contains $2d-3$ precolored edges, so
exactly one plane $D_{i}$, $i\neq 1,2$ has exactly one precolored edge
$a_{i}$; we assume $i\neq 3$. Then as in Claim 4.6, there is either

  * (i)

an edge $e^{\prime}_{1}\in E(Q_{1})$ incident with $u_{1}$ but not $u_{2}$,
such that $e^{\prime}_{1}$ and the corresponding edge $e^{\prime\prime}_{1}$
of $Q_{2}$ are uncolored, and not adjacent to any edge in $Q_{1}\cup Q_{2}$
colored $c_{1}$, or

  * (ii)

an edge $e^{\prime}_{2}\in E(Q_{1})$ incident with $u_{2}$ but not $u_{1}$,
such that $e^{\prime}_{2}$ and the corresponding edge $e^{\prime\prime}_{2}$
of $Q_{2}$ are uncolored, and not adjacent to any edge in $Q_{1}\cup Q_{2}$
colored $c_{2}$.

Suppose e.g. that (ii) holds. Then we define a new precoloring
$\varphi^{\prime}$ from the restriction of $\varphi$ to $Q_{1}\cup Q_{2}$ by
coloring $e^{\prime}_{2}$ and $e^{\prime\prime}_{2}$ by the color $c_{2}$. By
removing the color $c_{1}$ from any edge that is colored $c_{1}$ under
$\varphi^{\prime}$, we obtain the precoloring $\varphi^{\prime\prime}$ of
$Q_{1}\cup Q_{2}$. Next, we take an extension of $\varphi^{\prime\prime}$
using colors $\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3}\\}$, and then recolor
all edges that are $\varphi$-colored $c_{1}$ by the color $c_{1}$ to obtain
the coloring $f$ which is an extension of $\varphi^{\prime}$. We color all
edges between $Q_{1}$ and $Q_{2}$ by the color $c_{3}$ except $e_{1}$ which is
colored $c_{1}$, color $Q_{3}$ correspondingly to how $Q_{2}$ is colored, and
color the edges between $Q_{2}$ and $Q_{3}$ by a color in
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3}\\}$ missing at its endpoints.

Next, consider the precolored edge $a_{i}$ of $Q_{i}$, and the corresponding
edge $a_{1}$ of $Q_{1}$. If $f(a_{1})=\varphi(a_{i})$, then we color all the
planes $Q_{4},\dots,Q_{2k+1}$ correspondingly to how $Q_{1}$ is colored.
Thereafter, we color the edges between $Q_{3}$ and $Q_{4}$ similarly to how
the edges between $Q_{1}$ and $Q_{2}$ are colored, and then color the
remaining uncolored paths in $D_{1}$ using two colors not appearing at the
endpoints of these paths. Finally, we swap colors on a bicolored $4$-cycle
containing $e_{2}$ to obtain an extension of $\varphi$.

Otherwise, if $f(a_{1})\neq\varphi(a_{i})$, then we color the planes
$Q_{4},\dots,Q_{2k+1}$ correspondingly to how $Q_{1}$ is colored, except that
we permute the colors $f(a_{1})$ and $\varphi(a_{i})$. Then we color the edges
between $Q_{3}$ and $Q_{4}$ with the color $c_{3}$, and consider the subgraph
$H$ consisting of the edges of $D_{1}$ with endpoints in two consecutive
planes in the sequence $Q_{4},\dots,Q_{2k+1},Q_{1}$. If we define a list
assignment for these edges by for every edge including the colors from
$\\{1,\dots,2d+1\\}$ that do not appear on any adjacent edges, then each edge,
except the ones with endpoints in $Q_{1}$ and $Q_{2k+1}$, gets a list of size
at least two. Hence, $H$ is list edge colorable from these lists. This yields
an edge coloring of $G$ that agrees with $\varphi$ except for $e_{2}$.
Finally, we swap colors on a bicolored $4$-cycle containing $e_{2}$ to obtain
an extension of $\varphi$.

Subcase 3.2.2 $e_{1}$ and $e_{2}$ are incident with exactly one common plane:

Suppose now instead that $e_{1}$ and $e_{2}$ are incident to exactly one
common plane, say $Q_{1}$, where $e_{1}$ in addition also is incident with
$Q_{2}$. If there are uncolored corresponding edges $e^{\prime}_{1}\in
E(Q_{1})$ and $e^{\prime}_{2k+1}\in E(Q_{2k+1})$ that are incident with
$e_{2}$ but not to any other edge precolored $c_{2}$, and similar edges for
$e_{1}$ and the color $c_{1}$ in $Q_{1}$ and $Q_{2}$, respectively, which are
disjoint from $e^{\prime}_{1}$, then we proceed as above: we can obtain an
extension by coloring the edges adjacent to $e_{1}$ and $e_{2}$ by colors
$c_{1}$ and $c_{2}$, respectively, and then proceed as in Case 3 of Lemma 4.2,
as before.

Now, any two adjacent planes contains at most $2d-3$ precolored edges, so if
there are no edges as described in the preceding paragraph, then all
precolored edges are contained in $Q_{2k+1}\cup Q_{1}\cup Q_{2}$, and $e_{1}$
and $e_{2}$ are adjacent to a common vertex $u_{1}\in V(Q_{1})$. Moreover,
$u_{1}$ is incident with $2d-4$ edges colored by distinct colors from
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2},c_{3},c_{4}\\}$, $Q_{2k+1}$
contains exactly one precolored edge, and $Q_{2}$ contains exactly one
precolored edge. Moreover, these precolored edges in $Q_{2k+1}\cup Q_{2}$ are
either adjacent to vertices corresponding to $u_{1}$, or colored $c_{2}$ and
$c_{1}$ respectively, and adjacent to edges that are incident with $u_{1}$. We
consider some different cases, depending on the colors of the precolored edges
of $Q_{1}$ and $Q_{2}$.

Suppose first that the precolored edge of $Q_{2k+1}$ is colored $c_{2}$, and
that $Q_{2}$ contains an edge precolored $c_{1}$. We color all edges of
$Q_{2k+1}$ adjacent to $e_{2}$ that are not precolored or adjacent to an edge
precolored $c_{2}$ by arbitrary colors from
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2},c_{3}\\}$ so that the resulting
precoloring is proper, and similarly for $Q_{2}$ but with $c_{1}$ in place of
$c_{2}$. Next, we take an extension of the resulting precoloring
$\varphi^{\prime}$ of $Q_{2k+1}\cup Q_{1}\cup Q_{2}$, where we use colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3}\\}$ for $Q_{2k+1}$,
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ for $Q_{1}$, and
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$ for $Q_{2}$. We then color the
edges between $Q_{2k+1}$ and $Q_{1}$ by $c_{1}$ except $e_{2}$ which is
colored $c_{2}$, the edges between $Q_{1}$ and $Q_{2}$ by $c_{2}$ except
$e_{1}$ which is colored $c_{1}$. Next, we color the planes
$Q_{3},\dots,Q_{2k}$ correspondingly using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{3},c_{4}\\}$, and all remaining uncolored
edges by $c_{3},c_{4}$ alternately. This yields an extension of $\varphi$.

Now, if one of the colors $c_{1}$ and $c_{2}$ does not appear in $G-E(D_{1})$,
say $c_{2}$, then from the restriction of $\varphi$ to $Q_{1}\cup Q_{2}$, we
define a new precoloring $\varphi^{\prime}$ by properly coloring all the edges
adjacent to $e_{1}$ that are not precolored or adjacent to an edge colored
$c_{1}$ by arbitrary colors in
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2},c_{3}\\}$ so that the resulting
coloring is proper. We take an extension of $\varphi^{\prime}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$, and an extension of the
restriction of $\varphi$ to $Q_{2k+1}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$. Thereafter, we color all edges
between $Q_{2k+1}$ and $Q_{1}$ by the color $c_{2}$, the edges between $Q_{1}$
and $Q_{2}$ by the color $c_{3}$ except that $e_{1}$ is colored $c_{1}$. Since
no other planes in $G-E(D_{1})$ contain precolored edges, it is now
straightforward to construct an extension of $\varphi$ from the obtained
partial edge coloring of $G$.

Finally, if the precolored edge of $Q_{2k+1}$ is colored $c_{1}$, and the edge
of $Q_{2}$ is colored $c_{2}$, then we proceed similarly, but simply take
extensions of the restriction of $\varphi$ to $Q_{2k+1}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{2},c_{3}\\}$, of the restriction of
$\varphi$ to $Q_{1}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{2}\\}$ and of the restriction of
$\varphi$ to $Q_{2}$ using colors
$\\{1,\dots,2d+1\\}\setminus\\{c_{1},c_{3}\\}$.

Subcase 3.2.3 $e_{1}$ and $e_{2}$ are not incident with any common plane:

It remains to consider the case when $e_{1}$ and $e_{2}$ are not incident to a
common plane. Here we may proceed precisely as in Subcase 3.1.3, so once again
we omit the details. This concludes the proof of this lemma. ∎

##  5 Extending a precoloring of a distance-$4$ matching in $C^{d}_{2k}$

In this last section we consider the problem of extending a precoloring of
$C^{d}_{2k}$ where the precolored edges form a matching.

######  Theorem 5.1.

If $\varphi$ is a $2d$-edge coloring of a distance-$4$ matching of
$G=C^{d}_{2k}$, then $\varphi$ can be extended to a proper $2d$-edge coloring
of $G$.

###### Proof.

Let $\varphi$ be a $2d$-edge precoloring of a distance-$4$ matching $M$ of
$G$, and let $D_{1},\dots D_{k}$ be the dimensions of $G$. We define the edge
coloring $f$ of $G$ by properly coloring all edges of $D_{j}$ by $2j-1$ and
$2j$, so that all corresponding edges have the same color. The resulting
coloring satisfies that every $4$-cycle in $G$ is bicolored since
corresponding edges have the same color.

We shall describe a procedure for obtaining a required coloring $f^{\prime}$
that agrees with $\varphi$. For all precolored edges we shall use
transformations on some bicolored $4$-cycles. As we shall see, if
$e,e^{\prime}\in M$, then the cycles used for transformations involving $e$
will be edge-disjoint from cycles used for $e^{\prime}$.

Consider an arbitrary precolored edge $e\in M$. We consider some different
cases.

  * (i)

If $f(e)=\varphi(e)$, then we are done;

  * (ii)

If $f(e)\neq\varphi(e)$, and there is a bicolored $4$-cycle containing $e$,
and where color $\varphi(e)$ appears, then we interchange colors on this
bicolored $4$-cycle;

  * (iii)

If none of the two previous conditions hold, then there are two edges $e_{1}$
and $e_{2}$, both of which are adjacent to $e$, and contained in the same
dimension as $e$, such that $\varphi(e)=f(e_{1})=f(e_{2})$. By interchanging
colors on two disjoint $4$-cycles, containing $e_{1}$ and $e_{2}$
respectively, we obtain a coloring $f_{1}$, where $e$ is contained in a
bicolored $4$-cycle with the color $\varphi(e)$. Thus by interchanging colors
on this $4$-cycle, we obtain a coloring $f_{2}$ satisfying that
$f_{2}(e)=\varphi(e)$.

Note that all edges used in the transformations (i) - (iii) are at distance at
most $1$ from $e$. Thus if $e$ and $e^{\prime}$ are distinct edges of $M$, and
we perform one of the transformations (i)-(iii) for both edges, then the edges
involved in the transformations concerning $e$ will be edge disjoint from the
ones used for $e^{\prime}$, since the precolored edges form a distance-$4$
matching.

Hence, we can repeat the above process for any precolored edge of $G$ to
obtain the required coloring $f^{\prime}$. ∎

We believe that Proposition 5.1 might be true if we precolor a distance-$3$
instead of a distance-$4$ matching, but if $e$ and $e^{\prime}$ are distinct
edges of $M$, then the edges involved in the transformations for $e$ may not
necessarily be disjoint from the one used for $e^{\prime}$, and thus we cannot
apply our technique here; we state the following conjecture.

######  Conjecture 5.2.

If $\varphi$ is an edge precoloring of a distance-$3$ matching of
$C^{d}_{2k}$, then $\varphi$ can be extended to a proper $4$-edge coloring of
$C^{d}_{2k}$.

Note that Proposition 5.1 becomes false if we precolor a distance-$2$
matching; for instance, consider a vertex $v$ of degree $2d$ such that every
edge incident with $v$ is uncolored but there is a fixed color
$c\in\\{1,\dots,2d\\}$ satisfying that every edge incident with $v$ is
adjacent to another edge colored $c$. If $f$ is an extension of $\varphi$,
then since $v$ has degree $2d$, exactly one edge incident with $v$ is colored
$c$, but such a coloring cannot be proper.

## Acknowledgements

Petros thank the International Science Program in Uppsala, Sweden, for
financial support. Casselgren was supported by a grant from the Swedish
Research council VR (2017-05077).

## References

  * [1] L.D. Andersen, A.J.W. Hilton, Thank Evans!, _Proc. London Math. Soc._ 47 (1983), 507–522.
  * [2] L.D. Andersen, A.J.W Hilton, Symmetric Latin square and complete graph analogues of the Evans conjecture, Journal of Combinatorial Designs 4 (1994), 197–252.
  * [3] A.S. Asratian, T.M.J. Denley, R. Häggkvist, _Bipartite graphs and their applications_ , Cambridge University Press, Cambridge, 1998.
  * [4] C.J. Casselgren, F.B. Petros, S.A. Fufa, Extending partial edge colorings of cartesian products of graphs, submitted.
  * [5] C.J. Casselgren, F.B. Petros, Edge precoloring extension of trees, Australasian Journal of Combinatorics 81 (2021), 233–244.
  * [6] C.J. Casselgren, F.B. Petros, Edge precoloring extension of trees II, Discussiones Mathematicae Graph Theory (in press).
  * [7] C.J. Casselgren, K. Markström, L.A. Pham, Precoloring extension of hypercubes, Journal of Graph Theory 95 (2020), 410–444.
  * [8] T.Easton, R.Gary Parker, On completing latin squares, Discrete Applied Mathematics 15 (2001), 167–181.
  * [9] K. Edwards, A. Girao, J. van den Heuvel, R.J. Kang, G.J. Puleo, J.-S. Sereni, Extension from Precoloured Sets of Edges, Electronic Journal of Combinatorics 25 (2018), P3.1, 28 pp.
  * [10] T. Evans, Embedding incomplete latin squares, _American Mathematical Monthly_ 67 (1960), 958–961.
  * [11] J. Fiala, NP-completeness of the edge precoloring extension problem on bipartite graphs, _Journal of Graph Theory_ 43 (2003), pp. 156–160.
  * [12] A. Girao, R.J. Kang, Precolouring extension of Vizing’s theorem, Journal of Graph Theor 92 (2019), 255–260.
  * [13] R. Häggkvist, A solution of the Evans conjecture for Latin squares of large size Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, 18, 495–513.
  * [14] O. Marcotte, P. Seymour, Extending an edge coloring Journal of Graph Theory 14 (1990), 565-–573.
  * [15] H.J. Ryser, A combinatorial theorem with an application to Latin squares, _Proceedings of the American Mathematical Society_ 2 (1951), 550–552.
  * [16] B. Smetaniuk, A new construction for Latin squares I. Proof of the Evans conjecture, _Ars Combinatoria_ 11 (1981), 155–172.