Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

Abstract

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If $V_{1},\ldots , V_{p}$ are the p parts of V(K(n, p)), then a holey k -factor of deficiency $V_{i}$ of K(n, p) is a k-factor of $K(n,p)-V_{i}$ for some i satisfying $1\le i \le p$. Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each $n \times n$ “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.

1 Introduction

A hamiltonian decomposition of a graph G is a partition of the edges of G into sets, each of which induces a spanning cycle, called a hamiltonian cycle. An early result on hamiltonian decompositions appeared in 1892 when Walecki [11] proved the famous result that the complete graph $K_{n}$ on n vertices has a hamiltonian decomposition if and only if n is odd. The corresponding result for the existence of hamiltonian decompositions of the complete p-partite graph K(n, p) with n vertices in each of p parts was settled in 1976 by Laskar and Auerbach [7], showing that such a decomposition exists if and only if $n(p-1)$ is even. A new technique called vertex amalgamations, which proved to be very useful in finding hamiltonian decompositions, was introduced 30 years ago by Hilton and Rodger [5, 6]. They used this technique to find alternative proofs of the aforementioned two results, and demonstrated the power of the technique by obtaining embeddings of edge-colorings into hamiltonian decompositions. In this context, a hamiltonian decomposition of G is represented as an edge-coloring of G in which each color class induces a hamiltonian cycle. Buchanan [3] in 1997 used amalgamations to prove that for any odd n, and any 2-regular spanning subgraph U of $K_{n}$, $K_{n}-E(U)$ has a hamiltonian decomposition. By generalizing amalgamation results, Leach and Rodger [8, 10] solved the corresponding problem for complete bipartite graphs, for complete tripartite graphs, and for complete multipartite graphs with any number of parts in the case when U has no cycles of small length. More recently, a neat observation using difference methods solved this and natural generalizations [2, 12]. The main tool used in this paper is Theorem 2.1, which is a special case of a general result on amalgamations that was proved by Bahmanian and Rodger [1] in 2011. Using Theorem 2.1 satisfies one of the aims of this work, namely to add to the literature demonstrating that interesting problems, proofs of which do not appear to be accessible using traditional techniques, can be solved by using amalgamations.

For any simple graph G, let $\lambda G$ denote the multigraph in which if two vertices are joined by $\epsilon \in \lbrace 0,1 \rbrace$ edges in G then they are joined by $\lambda \epsilon$ edges in $\lambda G$. Then, an edge-coloring of $\lambda K(n,p)$ is said to be fair if for each pair of parts $V_{x}$ and $V_{y}$ and for each pair of colors i and j, $||c_{i}(V_{x}, V_{y})| - |c_{j}(V_{x}, V_{y})|| \le 1$, where $c_{i}(V_{x}, V_{y})$ denotes the set of edges colored i between $V_{x}$ and $V_{y}$. In 2002 Leach and Rodger [9] completely settled the existence problem for fair hamiltonian decompositions of K(n, p), showing that they exist if and only if $n(p-1)$ is even.

The main aim of this paper is to extend these results on fair hamiltonian cycle decompositions to other natural decompositions of K(n, p) described below. A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. For each $v\in V(G)$, a k-factor of $G-v$ is said to be an almost parallel class (or near k-factor) of G with deficiency v. An almost resolvable k-factorization of G is a partition of E(G) into almost parallel classes each of which is a k-factor of $G-v$ for some $v\in V(G)$. If $V_{1}, \ldots , V_{p}$ are the p parts of V(K(n, p)), then a holey k-factor of deficiency $V_{i}$ of K(n, p) is a k-factor of $K(n,p)-V_{i}$ for some i satisfying $1\le i \le p$. Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). It is useful to represent a holey 1-factorization of K(n, p) as an edge-coloring of K(n, p): an edge-coloring of K(n, p) is said to be a holey edge-coloring if each color class induces a holey 1-factor of K(n, p). In deciding if a holey edge-coloring is fair, the permitted colors on edges joining vertices in $V_{i}$ and $V_{j}$ are the colors occurring on holey 1-factors of deficiency other than $V_{i}$ or $V_{j}$. In this paper the existence of fair 1-factorizations of K(n, p) is completely settled (see Theorem 4.1), as is the existence of fair holey 1-factorizations of K(n, p) (see Theorem 4.2).

It is not hard to see that from a design theoretic perspective a holey 1-factorization of K(n, p) is the same as a (2, 1)-frame of type $n^{p}$ (for a definition, see page 261 of [4]). Indeed, there is a clear one-to-one correspondence between holey 1-factorizations of K(n, p) and symmetric quasigroups of order np with holes of size n: cells (i, j) and (j, i) are filled with symbol k if and only if the edge $\lbrace i,j \rbrace$ is colored k. Such quasigroups can often be constructed using direct products, but in so doing the edge coloring corresponding to the resulting quasigroup is as far as possible from being fair. The following two quasigroups of order 20 with holes of size 4 are constructed using the well-known direct product construction and the fair holey 1-factorization of K(4, 5) obtained from the construction described in the proof of Theorem 4.2, respectively. Comparing these two quasigroups, the effect of the fair property is clearly seen in the $4\times 4$ “boxes” of the latter quasigroup, in which each permitted symbol appears once or twice in each such “box”, as opposed to the direct product construction, which produces a quasigroup in which each permitted symbol appears 0 or 4 times in each $4\times 4$ “box”.

Notice that it is possible to complete these partial quasigroups to complete quasigroups by using disjoint subquasigroups of order 4 to fill in the holes. Doing so might seem to go against the spirit of the fairness property. In considering this point, it is important to note that holey quasigroups have been critically important structures that play a role when complete quasigroups cannot exist, and that is the case here. Since we require the structure we construct to be symmetric, except in some extremely special situations it is therefore impossible for the diagonal subsquares (i.e. currently the holes) to have the property we seek if they were to be filled, each symbol necessarily occurring an even number of times in the off-diagonal cells. But allowing holes to appear in the diagonal positions is the structure that allowed for big breakthroughs during the 1980’s, where holey structures were exactly the right way to deal with situations like this where the desired property could never occur in the diagonal positions, but could be guaranteed to be satisfied elsewhere. (Most closely related to this observation is the fact that idempotent symmetric quasigroups of even order do not exist, but symmetric quasigroups with holes of size 2 do exist.)

It may also be worth giving an example of the type of partial quasigroup one can obtain from a fair 1-factorization of K(n, p).

Notice that again one could complete this partial quasigroup to a complete quasigroup by filling the holes with quasigroups of size 2, but in this case all of them would be on the same set of symbols rather than being disjoint. As before, such diagonal quasigroups are necessarily unfair in all but some extremely special situations.

We present some notation that will be used throughout the paper. Usually the vertex set of $\lambda K_{p}$ will be $\lbrace \infty \rbrace \cup {\mathbb {Z}}_{p-1}$. Since difference methods will be usefully employed, define $\infty + t = \infty$ and $(c_{0}, c_{1}, \ldots , c_{n-2})_{z} + t = (c_{0}+t, c_{1}+t, \ldots , c_{n-2}+t)$, with sums reduced modulo z. Also, define $f((c_{0}, c_{1}, \ldots , c_{n-2})) = (f(c_{0}), \ldots , f(c_{n-2}))$ where $f: V(G) \rightarrow V(G)$. The edge $\lbrace a,b \rbrace \subseteq {\mathbb {Z}}_{n}$ with $a < b$ is said to have difference $D_{n}(a,b) = \min \lbrace b-a, n-(b-a) \rbrace$, and the edge $\lbrace a, \infty \rbrace$ is said to have difference $\infty$. It will be convenient for each $a \in {\mathbb {Z}}_{n} {\setminus } \lbrace 0\rbrace$ to define $D_{n}(a) = \min \lbrace a, n-a \rbrace$. For each $d\in {\mathbb {Z}}_{n} {\setminus } \lbrace 0\rbrace$, let $S_{d}$ be the 2-factor of $2K_{n}$ on the vertex set ${\mathbb {Z}}_{n}$ induced by the edges in the multiset $\lbrace \lbrace i, i+d \rbrace \mid i \in {\mathbb {Z}}_{n} \rbrace$, reducing the sums modulo n (so $S_{d} = S_{n-d}$).

2 Amalgamations

A graph H is said to be an amalgamation of a graph G if there exists a function $\psi$ from V(G) onto V(H) and a bijection $\psi ^{\prime }: E(G)\rightarrow E(H)$ such that $e=\lbrace u,v \rbrace \in E(G)$ if and only if $\psi ^{\prime }(e)=\lbrace \psi (u),\psi (v) \rbrace \in E(H)$. The function $\psi$ is called an amalgamation function. We say that G is a detachment of H, where each vertex v of H splits into the vertices of $\psi ^{-1}(\lbrace v \rbrace )$. An n-detachment of H is a detachment in which each vertex of H splits into n vertices. Amalgamating a finite graph G to form the corresponding amalgamated graph H can be thought of as grouping the vertices of G and forming one supervertex for each such group by squashing together the original vertices in the same group. An edge incident with a vertex in G is then incident with the corresponding new vertex in H; in particular an edge joining two vertices from the same group becomes a loop on the corresponding new vertex in H.

In what follows, G(j) denotes the subgraph of G induced by the edges colored j, $d_{G}(u)$ denotes the degree of vertex u in G, and $m_{G}(u,v)$ denotes the number of edges between u and v in G. The following theorem was proved in much more generality by Bahmanian and Rodger in [1], but this is sufficient for our purposes.

Theorem 2.1

Let H be a k-edge-colored loopless graph. Then there exists an n-detachment G of H with amalgamation function $\psi : V(G) \rightarrow V(H)$ such that G satisfies the following properties : 

• (i) $d_{G}(u) \in \lbrace \lfloor d_{H}(w)/n \rfloor , \lceil d_{H}(w)/n \rceil \rbrace$ for each $w \in V(H)$ and each $u \in \psi ^{-1}(w);$

• (ii) $d_{G(j)}(u) \in \lbrace \lfloor d_{H(j)}(w)/n \rfloor , \lceil d_{H(j)}(w)/n \rceil \rbrace$ for each $w \in V(H)$ and each $u \in \psi ^{-1}(w)$ and each $j \in {\mathbb {Z}}_{k};$

• (iii) $m_{G}(u,v) \in \lbrace \lfloor m_{H}(w,z)/n^{2} \rfloor , \lceil m_{H}(w,z)/n^{2} \rceil \rbrace$ for every pair of distinct vertices $w,z \in V(H),$ each $u\in \psi ^{-1}(w)$ and each $v\in \psi ^{-1}(z)$.

We will use the following immediate corollaries of this result.

Corollary 2.2

If there exists a fair $n(p-1)$-edge-coloring of $n^{2}K_{p}$ in which each color class is n-regular,  then there exists a fair 1-factorization of K(n, p).

Proof

Using the notation in Theorem 2.1, let $H = n^{2}K_{p}$. Then by Theorem 2.1 there exists an n-detachment G of H such that

• (i) the degree of each vertex in G is $n(p-1)$,

• (ii) each color class induces a spanning 1-regular subgraph (since we are given that $d_{H(j)}(w) = n$ for each $w \in V(H)$ and $j \in {\mathbb {Z}}_{n(p-1)}$), and

• (iii) there is exactly one edge between each pair of vertices u and v of G for which $\psi (u) \ne \psi (v)$, and no edges otherwise.

So, by (i) and (iii) it is clear that $G=K(n,p)$ with partition $\lbrace \psi ^{-1}(w) \mid w \in V(H) \rbrace$ of the vertex set, and by (ii) each color class induces a 1-factor of K(n, p). This yields a 1-factorization of K(n, p). There is a one-to-one correspondence between the edges joining any pair of vertices w and z in H and the edges between the two corresponding parts of $G=K(n,p)$, one of which contains the vertices in $\psi ^{-1}(w)$ and the other one contains the vertices in $\psi ^{-1}(z)$. Hence a fair edge-coloring of $n^{2}K_{p}$ (in which the parts all have size 1) results in a fair edge-coloring of K(n, p). $\square$

Corollary 2.3

If there exists a fair holey n-factorization of $n^{2}K_{p}$ (np-edge-coloring of $n^{2}K_{p}$ in which each color class is an n-regular subgraph of $n^{2}K_{p}-v$ for some $v\in V(n^{2}K_{p}))$ then there exists a fair holey 1-factorization of K(n, p).

Proof

Using the notation in Theorem 2.1, let $H = n^{2}K_{p}$. Then by Theorem 2.1 there exists an n-detachment G of H such that

• (i) the degree of each vertex in G is $n(p-1)$,

• (ii) each color class induces a spanning 1-regular subgraph of $G-\psi ^{-1}(v)$ for some $v \in V(H)$ (since we are given that $d_{H(j)}(w) = n$ for each $w \in V(H) {\setminus } \lbrace v \rbrace$ for some vertex $v \in V(H)$), and

• (iii) there is exactly one edge between each pair of vertices u and w of G for which $\psi (u) \ne \psi (w)$, and no edges otherwise.

So, by (i) and (iii) it is clear that $G=K(n,p)$ with partition $\lbrace \psi ^{-1}(w)\mid w\in V(H) \rbrace$ of the vertex set, and by (ii) that each color class induces a holey 1-factor of K(n, p). This yields a holey 1-factorization of K(n, p). There is a one-to-one correspondence between the edges colored c joining any pair of vertices u and w in H and the edges colored c between the two corresponding parts $\psi ^{-1}(u)$ and $\psi ^{-1}(w)$ of $G=K(n,p)$, so this fair edge-coloring of $n^{2}K_{p}$ results in a fair holey edge-coloring of K(n, p) as required. $\square$

3 Coloring Results

In this section the coloring results are obtained that allow Theorems 4.1 and 4.2 to be deduced from Corollaries 2.2 and 2.3, respectively.

Proposition 3.1

Suppose np is even. There exists an edge-coloring of $n^{2}K_{p}$ with $n(p-1)$ colors such that

• (i) the edge-coloring is fair,  and

• (ii) each color class induces an n-regular subgraph.

Proof

First note that condition (i) is equivalent to requiring that between each pair of vertices each color appears on $\lfloor n^{2}/(n(p-1)) \rfloor$ or $\lceil n^{2}/(n(p-1)) \rceil$ edges.

Now suppose that p is even. Then clearly, $K_{p}$ has a 1-factorization consisting of $p-1$ 1-factors $F_{0}, F_{1}, \ldots ,F_{p-2}$. Let $F=(F_{0}, F_{1}, \ldots , F_{n^{2}(p-1)-1})$ be a sequence of $n^{2}(p-1)$ 1-factors of $K_{p}$ where $F_{i}=F_{j}$ if $i\equiv j$ modulo $p-1$. For each $i\in {\mathbb {Z}}_{n(p-1)}$, let G(i) be the subgraph induced by the edges in $\bigcup _{j=in}^{(i+1)n-1}F_{j}$, and color all edges in G(i) with i. Then $\lbrace E(G(i)) \mid i \in {\mathbb {Z}}_{n(p-1)}\rbrace$ is a partition of the edge set of $n^{2}K_{p}$. Clearly this coloring of $n^{2}K_{p}$ satisfies condition (ii). To see that it also satisfies condition (i), note that for each $i \in {\mathbb {Z}}_{n(p-1)-(p-1)}$, $\lbrace F_{i+j}\mid j\in {\mathbb {Z}}_{p-1} \rbrace$ is a 1-factorization of $K_{p}$. So for each $i \in {\mathbb {Z}}_{n(p-1)}$, the n(p / 2) edges colored i are shared as evenly as possible among the $p(p-1)/2$ pairs of vertices, so the number of edges colored i between each pair of vertices is $\lfloor (np/2)/(p(p-1)/2) \rfloor = \lfloor n/(p-1) \rfloor$ or $\lceil (np/2)/(p(p-1)/2)\rceil = \lceil n/(p-1)\rceil$ as required.

Finally, suppose that p is odd. Then n is even since we are given that np is even. $K_{p}$ has a 2-factorization consisting of $(p-1)/2$ 2-factors $F_{0}, F_{1}, \ldots ,F_{(p-3)/2}$ (by Petersen’s Theorem [13]). Let $F=(F_{0}, F_{1}, \ldots , F_{n^{2}(p-1)/2-1})$ be a sequence of $n^{2}(p-1)/2$ 2-factors of $K_{p}$ where $F_{i}=F_{j}$ if $i\equiv j$ modulo $(p-1)/2$. For each $i\in {\mathbb {Z}}_{n(p-1)}$, let G(i) be the subgraph induced by the edges in $\bigcup _{j=in/2}^{(i+1)n/2-1}F_{j}$, and color all edges in G(i) with i. Then $\lbrace E(G(i)) \mid i \in {\mathbb {Z}}_{n(p-1)}\rbrace$ is a partition of the edge set of $n^{2}K_{p}$. Clearly this coloring of $n^{2}K_{p}$ satisfies condition (ii). To see that it also satisfies condition (i), note that for each $i \in {\mathbb {Z}}_{n(p-1)-(p-1)}$, $\lbrace F_{i+j}\mid j\in {\mathbb {Z}}_{p-1} \rbrace$ is a 2-factorization of $K_{p}$, so for each $i \in {\mathbb {Z}}_{n(p-1)}$, the (n / 2)p edges colored i are shared as evenly as possible among the $p(p-1)/2$ pairs of vertices. $\square$

Proposition 3.2

Suppose $p>2$ is even. There exists a set ${\mathcal {F}} = \lbrace F_{d}\mid d \in {\mathbb {Z}}_{(p-2)/2} \rbrace$ of $(p-2)/2$ almost resolvable 2-factorizations of $2K_{p}$ such that for each vertex $v\in V(2K_{p}),$

• (i) the almost parallel classes in $\bigcup _{F\in {\mathcal {F}}}F$ with deficiency v form a 2-factorization of $K_{p-1}$.

Proof

Let $V(2K_{p})={\mathbb {Z}}_{p-1} \cup \lbrace \infty \rbrace$. Define the $(p-1)$-cycle $C = (c_{0},c_{1}, \ldots ,c_{p-2})$ by

$$\begin{aligned} c_{i}= {\left\{ \begin{array}{ll} 1 &{}\text {if }i=0 \\ (i+3)/2 &{}\text {if }i\text { is odd} \\ (p-1)-(i/2) &{}\text {if }i\text { is even and }i \notin \lbrace 0, p-2 \rbrace \\ \infty &{}\text {if }i=p-2. \end{array}\right. } \end{aligned}$$

Then C has deficiency 0 and contains two edges of each difference in $({\mathbb {Z}}_{(p-2)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for just one edge of difference 2. Therefore $F_{0}=\lbrace C+t\mid t \in {\mathbb {Z}}_{p-1} \rbrace \cup \lbrace S_{2} \rbrace$ is an almost resolvable 2-factorization of $2K_{p}$, where $C+t$ has deficiency t and $S_{2}$ has deficiency $\infty$.

To construct the remaining almost resolvable 2-factorizations of $2K_{p}$, for $1\le d \le (p-4)/2$ define the $(p-1)$-cycle $g_{d}(C) = (g_{d}(c_{0}), g_{d}(c_{1}), \ldots , g_{d}(c_{p-2}))$ where

$$\begin{aligned} g_{d}(c_{i}) = {\left\{ \begin{array}{ll} c_{i}+d+1 &{} \text {if }i\in \lbrace 2j \mid 1 \le j \le d \rbrace \\ c_{i}+d &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

with additions defined modulo $p-1$. Clearly, since C is a cycle, $g_{d}(C)$ is also a cycle on the same vertex set as C, namely $V(C)=({\mathbb {Z}}_{p-1} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$. Also define $g_{0}(C)=C$. Then for each $d \in {\mathbb {Z}}_{(p-2)/2}$, $g_{d}(C)$ has deficiency 0 and contains two edges of each difference in ${\mathbb {Z}}_{(p-2)/2} \cup \lbrace \infty \rbrace$, except for just one edge of difference $D_{p-1}(2d+2)$. Therefore, for each $d\in {\mathbb {Z}}_{(p-2)/2}$, $F_{d} = \lbrace g_{d}(C) + t \mid t \in {\mathbb {Z}}_{p-1} \rbrace \cup \lbrace S_{2d+2} \rbrace$ is an almost resolvable 2-factorization of $2K_{p}$.

Now we show that for each $v \in V(2K_{p})$, the almost parallel classes in $\bigcup _{d \in {\mathbb {Z}}_{(p-2)/2}}F_{d}$ with deficiency v form a 2-factorization of $K_{p-1}$.

First suppose $v = \infty$. Since $p-1$ is odd and since $S_{d} = S_{p-1-d}$, $\lbrace S_{2d+2} \mid d \in {\mathbb {Z}}_{(p-2)/2} \rbrace = \lbrace S_{1}, S_{2}, \ldots , S_{(p-2)/2} \rbrace$. Hence these almost parallel classes with deficiency $\infty$ form a 2-factorization of $K_{p}{\setminus } \lbrace \infty \rbrace$.

Next suppose $v=0$. For each $w\in {\mathbb {Z}}_{p-1}{\setminus } \lbrace 0 \rbrace$, let $N(w) = (1, 2, \ldots , w-1, \infty , w+1, \ldots , p-2) = (N_{0}, N_{1}, \ldots , N_{p-3})$. For each $w\in {\mathbb {Z}}_{p-1} {\setminus } \lbrace 0 \rbrace$ and each $d \in {\mathbb {Z}}_{(p-2)/2}$, for some $i\in {\mathbb {Z}}_{p-1}$ the neighbors of w in $g_{0}(C)$ are $N_{i}$ and $N_{i+1}$, and so then with this value i in mind it is easy to check that the neighbors of w in $g_{d}(C)$ are $N_{i+2d}$ and $N_{i+2d+1}$, reducing the sums in the subscript modulo $p-2$. So,

• ($\dagger$) $\lbrace g_{d}(C)\mid d\in {\mathbb {Z}}_{(p-2)/2}\rbrace$ is a 2-factorization of $K_{p-1}$ on the vertex set $({\mathbb {Z}}_{p-1}{\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$.

Finally, for each $v \in {\mathbb {Z}}_{p-1}$, the almost parallel classes with deficiency v are $\lbrace g_{d}(C)+v \mid d\in {\mathbb {Z}}_{(p-2)/2}\rbrace$, which by ($\dagger$) is clearly a 2-factorization of $K_{p-1}$ on the vertex set $({\mathbb {Z}}_{p-1}{\setminus } \lbrace v \rbrace ) \cup \lbrace \infty \rbrace$. $\square$

In the following lemma, condition (iii) will be of use in the case where n is even and condition (iv) will be needed when n is odd when proving Theorem 4.2.

Proposition 3.3

Suppose $p>1$ is odd. There exists a set ${\mathcal {F}} = \lbrace F_{d}\mid d \in {\mathbb {Z}}_{p-2} \rbrace$ of $p-2$ almost resolvable 2-factorizations of $2K_{p}$ such that for each vertex $v\in V(2K_{p})$

• (i) the almost parallel classes in $\bigcup _{F\in {\mathcal {F}}}F$ with deficiency v form a 2-factorization of $2K_{p-1},$

• (ii) there exists ${\mathcal {F}}^{\prime } \subset \mathcal {F}$ such that $\mid {\mathcal {F}}^{\prime } \mid = (p-3)/2$ and the almost parallel classes with deficiency v in ${\mathcal {F}}^{\prime }$ are edge-disjoint, 

• (iii) there exists $F\in {\mathcal {F}} {\setminus } {\mathcal {F}}^{\prime }$ such that for each $v\in V$ each edge in $K_{p-1}$ on the vertex set $V{\setminus } \lbrace v \rbrace$ occurs in a 2-factor in $\mathcal {F}^{\prime } \cup \lbrace F \rbrace ,$ and

• (iv) there exists an almost resolvable 1-factorization $F^{1}$ of $K_{p}$ such that for each $v \in V(2K_{p})$ the almost parallel class with deficiency v in $F^{1}$ together with the almost parallel classes in ${\mathcal {F}}^{\prime }$ with deficiency v partition the edges of $K_{p-1}$ on the vertex set $V{\setminus } \lbrace v \rbrace$.

Proof

We begin by defining ${\mathcal {F}}$ on the vertex set $V={\mathbb {Z}}_{p-1} \cup \lbrace \infty \rbrace$. Define the $(p-1)$-cycle $C = (c_{0},c_{1}, \ldots ,c_{p-2})$ by

$$\begin{aligned} c_{i}= {\left\{ \begin{array}{ll} 1 &{} \text {if }i=0 \\ (i+3)/2 &{} \text {if }i\text { is odd and }i \ne p-2 \\ (p-1)-(i/2) &{} \text {if }i\text { is even and }i \ne 0 \\ \infty &{} \text {if }i=p-2, \end{array}\right. } \end{aligned}$$

with all arithmetic reduced modulo $p-1$. Then C has deficiency 0 and contains two edges of each difference in ${\mathbb {Z}}_{(p-1)/2} \cup \lbrace \infty \rbrace$, except for just one edge of each of the differences 2 and $(p-1)/2$. Therefore $F_{0}=\lbrace C+v\mid v \in {\mathbb {Z}}_{p-1} \rbrace \cup \lbrace S_{2} \rbrace$ is an almost resolvable $2-$factorization of $2K_{p}$, where $C+v$ has deficiency v and $S_{2}$ has deficiency $\infty$ (each edge of difference $(p-1)/2$ appears twice in the cycles in $F_{0}$ since the edge $e=\lbrace x, x+(p-1)/2 \rbrace$ is the same as the edge $e + v$ when $v= (p-1)/2$).

To construct the remaining almost resolvable 2-factorizations of $2K_{p}$, for $1\le d \le (p-3)/2$ define the $(p-1)$-cycle $g_{d}(C)$ where

$$\begin{aligned} g_{d}(c_{i}) = {\left\{ \begin{array}{ll} c_{i}+d+1 &{} \text {if }i\in \lbrace 2j \mid 1 \le j \le d \rbrace \\ c_{i}+d &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$

and for $(p-1)/2 \le d \le p-3$ define $g_{d}(C)$ as

$$\begin{aligned} g_{d}(c_{i}) = {\left\{ \begin{array}{ll} c_{i}+d+1 &{} \text {if }i\ne 0\text { is even or }i\in \lbrace p-2j \mid 2 \le j \le d-(p-5)/2 \rbrace \\ c_{i}+d &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$

with additions defined modulo $p-1$. Also define $g_{0}(C)=C$. Then for each $d \in {\mathbb {Z}}_{p-2}$, $g_{d}(C)$ has deficiency 0. For each $d \in {\mathbb {Z}}_{p-2}$, define $m_{p}(d)$ as follows.

Suppose $p=4k+1$ for some integer k. If $0 \le d \le 2k-2$ and $d\ne k-1$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for just one edge of each of the two differences $m_{p}(d)=D_{p-1}(2d+2)$ and $(p-1)/2$. If $d = k-1$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for no edge of difference $m_{p}(d)=(p-1)/2$. If $2k-1 \le d \le 3k-2$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for just one edge of each of the two differences $m_{p}(d)=2d-4k+3$ and $(p-1)/2$. If $3k-1 \le d \le 4k-2$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for just one edge of each of the two differences $m_{p}(d)=8k-2d-3$ and $(p-1)/2$. Notice that: $\lbrace m_{p}(d) \mid 0 \le d \le 2k-2, d \ne k-1 \rbrace$ is the multiset consisting of two copies of each even difference except for the difference $(p-1)/2$; $m_{p}(k-1) = (p-1)/2$; and each of $\lbrace m_{p}(d) \mid 2k-1 \le d \le 3k-2 \rbrace$ and $\lbrace m_{p}(d) \mid 3k-1 \le d \le 4k-2 \rbrace$ is the set consisting of one copy of each odd difference. Hence $\lbrace S_{m} \mid m = m_{p}(d), d\in {\mathbb {Z}}_{p-2} \rbrace$ is a 2-factorization of $2K_{p-1}$ on the vertex set $V {\setminus } \lbrace 0 \rbrace$.

Suppose $p=4k+3$ for some integer k. If $0 \le d \le 2k-1$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for just one edge of each of the two differences $m_{p}(d)=D_{p-1}(2d+2)$ and $(p-1)/2$. If $2k \le d \le 4k$ and $d \ne 3k$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for just one edge of each of the two differences $m_{p}(d)=2k + 1 - 2|d-3k|$ and $(p-1)/2$. If $d = 3k$ then $g_{d}(C)$ contains two edges of each difference in $({\mathbb {Z}}_{(p+1)/2} {\setminus } \lbrace 0 \rbrace ) \cup \lbrace \infty \rbrace$, except for no edge of difference $m_{p}(d)=(p-1)/2$. Again notice that: $\lbrace m_{p}(d) \mid 0 \le d \le 2k-1 \rbrace$ is the multiset consisting of two copies of each even difference; each of $\lbrace m_{p}(d) \mid 2k \le d \le 3k-1 \rbrace$ and $\lbrace m_{p}(d) \mid 3k+1 \le d \le 4k \rbrace$ is the set consisting of one copy of each odd difference except for the difference $(p-1)/2$; and $m_{p}(3k) = (p-1)/2$. Hence $\lbrace S_{m} \mid m = m_{p}(d), d\in {\mathbb {Z}}_{p-2} \rbrace$ is a 2-factorization of $2K_{p-1}$ on the vertex set $V {\setminus } \lbrace 0 \rbrace$.

Therefore, for each $d\in {\mathbb {Z}}_{p-2}$, $F_{d} = \lbrace g_{d}(C) + v \mid v \in {\mathbb {Z}}_{p-1} \rbrace \cup \lbrace S_{m_{p}(d)} \rbrace$ is an almost resolvable 2-factorization of $2K_{p}$. (Recall that $S_{(p-1)/2}$ is the 2-factor of $2K_{p-1}$ in which each edge of difference $(p-1)/2$ appears twice.)

For each $d\in {\mathbb {Z}}_{p-2}$, $g_{d}(C)$ is a cycle on the vertex set $V= {\mathbb {Z}}_{p-1} \cup \lbrace \infty \rbrace$ with deficiency 0. Let $H_{d}$ be formed from $g_{d}(C)$ by removing the vertex 0 and renaming vertex i with $i-1$ for $1\le i\le p-2$. There is a clear one-to-one correspondence between $E(g_{d}(C))$ and $E(H_{d})$, so showing that $\lbrace H_{d} \mid d \in {\mathbb {Z}}_{p-2}\rbrace$ is a 2-factorization of $2K_{p-1}$ proves condition (i) for the case $v=0$. Under this bijection, for each $d\in {\mathbb {Z}}_{p-2}$, the near 2-factor $g_{d}(C)$ corresponds to the 2-factor $h_{d}=(h_{d}(0), \ldots , h_{d}(p-2))$ where

$$\begin{aligned} h_{d}(i) = {\left\{ \begin{array}{ll} (-1)^{i+1}\lceil i/2 \rceil +d &{} \text {if }\ i\in {\mathbb {Z}}_{p-2} \\ \infty &{} \text {if }\ i = p-2, \end{array}\right. } \end{aligned}$$

with all arithmetic reduced to modulo $p-2$. So $H_{d}$ is a hamiltonian cycle formed in a way similar to Walecki’s construction, and so clearly $\lbrace H_{d} \mid d \in {\mathbb {Z}}_{p-2}\rbrace$ is a hamiltonian decomposition of $2K_{p-1}$. For each $v\in {\mathbb {Z}}_{p-1}$, since $g_{d}(C)+v \equiv g_{d}(C)$, the same argument used when $v=0$ shows that $\lbrace g_{d}(C)+v \mid d \in {\mathbb {Z}}_{p-2} \rbrace$ provides the 2-factorization required by condition (i) for the case where the deficiency is $v\in {\mathbb {Z}}_{p-1}$. Finally, note that the near 2-factors with deficiency $v=\infty$, namely those in $\lbrace S_{m} \mid m = m_{p}(d), d\in {\mathbb {Z}}_{p-2} \rbrace$, form a 2-factorization of $2K_{p-1}$. So, condition (i) is satisfied for all $v\in {\mathbb {Z}}_{p-1} \cup \lbrace \infty \rbrace$.

We now consider condition (ii). Clearly, the cycles $g_{d}(C)$ with deficiency 0 are edge-disjoint for any set of $(p-3)/2$ consecutive values of d. Similarly, the cycles $g_{d}(C)+v$ with deficiency v where $v\in {\mathbb {Z}}_{p-1}$ are edge-disjoint for any set of $(p-3)/2$ consecutive values of d. In order to guarantee that the near 2-factors with deficiency $v = \infty$ are also edge-disjoint we must avoid $S_{(p-1)/2}$ (since it contains two copies of each edge). Therefore, recalling that $p \in \{4k+1, 4k+3\}$, we can define ${\mathcal {F}}^{\prime } = \lbrace F_{k}, F_{k+1}, \ldots , F_{k+(p-5)/2} \rbrace$, which provides (ii). Notice that

• ($\ddagger$) the near 2-factors in $F_{k}, F_{k+1}, \ldots , F_{k+(p-5)/2}$ with deficiency $v \ne \infty$ each contain two edges of each difference, except for one edge of difference $2(k-1), 2(k-2), \ldots , 2, 1, 3, \ldots , 2k-1$ respectively if $p=4k+1$, and except for one edge of difference $2k, 2(k-1), \ldots , 2, 1, 3, \ldots , 2k-1$ respectively if $p=4k+3$.

To see that condition (iii) is satisfied, first note that if $v\in {\mathbb {Z}}_{p-1}$ then each edge in $K_{p-1}$ on the vertex set $V{\setminus } \lbrace v \rbrace$ occurs in one of the cycles $g_{d}(C)+v$ for any $(p-1)/2$ consecutive values of d. So, defining $F=F_{k-1}$ and $F=F_{3k}=F_{k+(p-3)/2}$ if $p=4k+1$ and if $p=4k+3$ respectively provides condition (iii), since in both cases the near 2-factor in F with deficiency $\infty$ is $S_{(p-1)/2}$.

Finally to show that condition (iv) is satisfied, for each $v\in {\mathbb {Z}}_{p-1}\cup \lbrace \infty \rbrace$ let F(v) be the near 2-factor in F with deficiency v, and let $F^{1}(v)$ be the subgraph of $K_{p}-v$ formed by the edges occurring in no near 2-factors with deficiency v in ${\mathcal {F}}^{\prime }$; so by (ii) and (iii) $F^{1}(v)$ is a subgraph of F(v). By (ii) and (iii), each vertex in $({\mathbb {Z}}_{p-1} \cup \lbrace \infty \rbrace ){\setminus } \lbrace v \rbrace$ must have degree 1 in $F^{1}(v)$, so $F^{1}(v)$ is a near 1-factor of $K_{p}$ with deficiency v. We now show that $F^{1}=\lbrace F^{1}(v) \mid v\in {\mathbb {Z}}_{p-1} \cup \lbrace \infty \rbrace \rbrace$ is the required near 1-factorization of $K_{p}$. Since $F^{1}(\infty ) = \lbrace \lbrace i, i+(p-1)/2 \rbrace \mid i\in {\mathbb {Z}}_{(p-1)/2}\rbrace$ uses all the edges of difference $(p-1)/2$ once, and since clearly for each $v \in {\mathbb {Z}}_{p-1}$ $F^{1}(v+1) = F^{1}(v) + 1$ (reducing the sums modulo $v-1$), it remains to show that the set of differences of the edges in $F^{1}(0)$ is $\lbrace 1, 2, \ldots , (p-3)/2 \rbrace \cup \lbrace \infty \rbrace$. To see this, note that by $(\ddagger )$ there are $(p-3)/2$ near 2-factors in ${\mathcal {F}}^{\prime }$ with deficiency 0 which together contain exactly $p-4$ edges of each of the differences in $D = \lbrace 1, 2, \ldots ,(p-3)/2 \rbrace$ and exactly $p-3$ edges of difference $\infty$. Since in the subgraph $K_{p} - v$ of $K_{p}$ there are exactly $p-3$ edges of difference $d \in D$ (two of the $p-1$ edges of difference d in $K_{p}$ are incident with v) and exactly $p-2$ edges of difference $\infty$ (one of the $p-1$ edges of difference $\infty$ in $K_{p}$ is incident with v), one edge of each difference in $D \cup \lbrace \infty \rbrace$ must appear in $F^{1}(0)$.

$\square$

4 Main Results

Theorem 4.1

There exists a fair 1-factorization of K(n, p) if and only if np is even.

Proof

If np is odd then K(n, p) has no 1-factors, so clearly no 1-factorization exists. If np is even then the result follows immediately by Proposition 3.1 and Corollary 2.2. $\square$

Theorem 4.2

There exists a fair holey 1-factorization of K(n, p) if and only if $n(p-1)$ is even and $p\ne 2$.

Proof

It is clear that K(n, p) has no holey 1-factors when $n(p-1)$ is odd. Also, no holey 1-factors exist in K(n, p) when $p=2$. So the necessity is clear.

The result is trivial if $p=1$, so to prove the sufficiency we can assume that $p \ge 3$.

First suppose that p and n are both even. By Proposition 3.2, there exist $(p-2)/2$ almost resolvable 2-factorizations of $2K_{p}$, say $F_{0}, \ldots , F_{(p-4)/2}$, on the vertex set ${\mathbb {Z}}_{p}$ such that for each $v \in {\mathbb {Z}}_{p}$ the almost parallel classes with deficiency v form a 2-factorization of $K_{p-1}$ on the vertex set ${\mathbb {Z}}_{p} {\setminus } \lbrace v \rbrace$. Extend this list by defining $F_{i} = F_{j}$ if and only if $i \equiv j$ (mod $(p-2)/2$). From this extended list, form a sequence $T= (T_{0}, \ldots , T_{(np/2)-1})$ of np / 2 almost parallel classes of $nK_{p}$ where for $0 \le i \le p-1$ and $0\le k \le (n/2)-1$, $T_{i+kp}$ is the almost parallel class in $F_{k}$ with deficiency i. For each $i \in {\mathbb {Z}}_{p}$ let G(i) be the subgraph of $n^{2}K_{p}$ induced by the edges in $\bigcup _{k=0}^{(n/2)-1}T_{i+kp}$, and color all edges in G(i) with i. To complete this coloring to an np-edge-coloring of $n^{2}K_{p}$, for each $i \in {\mathbb {Z}}_{p}$ and $j \in {\mathbb {Z}}_{np}$, let $G(j) = G(i)$ if $i \equiv j$ (mod p). Then color class i consists of the $n(p-1)/2$ edges of n / 2 almost parallel classes which all have the same deficiency i for some $i\in V(K_{p})$, and hence each color class is an n-regular subgraph of $n^{2}K_{p}-i$. Furthermore, by condition (i) of Proposition 3.2, the $n(p-1)/2$ edges in each color class are shared out evenly among the $(p-1)(p-2)/2$ pairs of vertices in ${\mathbb {Z}}_{p} {\setminus } \lbrace i \rbrace$, so between any such pair of vertices there are $\lceil (n(p-1)/2)/((p-1)(p-2)/2) \rceil = \lceil n/(p-2)\rceil$ or $\lfloor (n(p-1)/2)/((p-1)(p-2)/2) \rfloor = \lfloor n/(p-2)\rfloor$ edges colored i.

Therefore this np-edge-coloring is fair. By Corollary 2.3 we conclude that there exists a fair holey 1-factorization of K(n, p).

Next suppose p is odd and n is even. By Proposition 3.3, there exist $p-2$ almost resolvable 2-factorizations of $2K_{p}$ on the vertex set ${\mathbb {Z}}_{p}$ such that

• 1. the almost parallel classes with deficiency v form a 2-factorization of $2K_{p-1}$,

and in which there exists a subset $\Sigma$ of $(p-1)/2$ almost resolvable 2-factorizations satisfying the two additional properties

• 2. for each $v \in {\mathbb {Z}}_{p}$, each edge of $K_{p}$ occurs in one of the $(p-1)/2$ almost parallel classes with deficiency v in $\Sigma$, and

• 3. $\Sigma$ contains $(p-3)/2$ almost resolvable 2-factorizations in which for each $v \in {\mathbb {Z}}_{p}$ the almost parallel classes with deficiency v are edge-disjoint.

Label the almost resolvable 2-factorizations of $2K_{p}$ with $F_{0}, \ldots , F_{p-3}$ such that for each $v \in {\mathbb {Z}}_{p}$ the almost parallel classes with deficiency v in $F_{0}, \ldots , F_{(p-5)/2}$ are edge-disjoint, and each edge of $K_{p-1}$ on the vertex set $V {\setminus } \lbrace v \rbrace$ is contained in at least one almost parallel class in $\lbrace F_{0}, \ldots , F_{(p-3)/2} \rbrace$. Extend this list by defining $F_{i}=F_{j}$ if $i \equiv j$ (mod $p-2$). From this extended list form a sequence $T= (T_{0}, \ldots , T_{(np/2)-1})$ of np / 2 almost parallel classes of $nK_{p}$ where for $0 \le i \le p-1$ and $0\le k \le (n/2)-1$, $T_{i+kp}$ is the almost parallel class in $F_{k}$ with deficiency i. For each $i \in {\mathbb {Z}}_{p}$ let G(i) be the subgraph of $n^{2}K_{p}$ induced by the edges in $\bigcup _{k=0}^{(n/2)-1}T_{i+kp}$, and color all edges in G(i) with i. To complete this coloring to an np-edge-coloring of $n^{2}K_{p}$, for each $i \in {\mathbb {Z}}_{p}$ and $j \in {\mathbb {Z}}_{np}$, let $G(j) = G(i)$ if $i \equiv j$ (mod p). Then color class i consists of the $n(p-1)/2$ edges of n / 2 almost parallel classes which all have the same deficiency i for some $i\in V(K_{p})$, and hence each color class is an n-regular subgraph of $n^{2}K_{p}-i$. Furthermore, by Proposition 3.3, the $n(p-1)/2$ edges in each color class are shared out evenly among the $(p-1)(p-2)/2$ pairs of vertices in ${\mathbb {Z}}_{p} {\setminus } \lbrace i \rbrace$, so between any such pair of vertices there are $\lceil (n(p-1)/2)/((p-1)(p-2)/2) \rceil = \lceil n/(p-2)\rceil$ or $\lfloor (n(p-1)/2)/((p-1)(p-2)/2) \rfloor = \lfloor n/(p-2)\rfloor$ edges colored i.

Therefore this np-edge-coloring is fair. By Corollary 2.3 we conclude that there exists a fair holey 1-factorization of K(n, p).

Finally suppose that p and n are both odd. By condition (iv) of Proposition 3.3 there exists an almost resolvable 1-factorization $F^{1}$ such that for each $v \in V(2K_{p})$ the almost parallel class with deficiency v in $F^{1}$, together with the almost parallel classes in ${\mathcal {F}}^{\prime }$ with deficiency v partition the edges of $K_{p-1}$ on the vertex set $V{\setminus } \lbrace v \rbrace$. Relabel the $(p-1)/2$ almost resolvable factorizations in ${\mathcal {F}}^{\prime } \cup \lbrace F^{1} \rbrace$ with $F_{0}, F_{1}, \ldots , F_{(p-3)/2}$ such that $F_{0} = F^{1}$. Extend this renaming so that $F_{i+(p-1)/2} = F_{(p-3)/2-i}$ for each $i \in {\mathbb {Z}}_{(p-1)/2}$ and so that $F_{i+j(p-1)} = F_{i}$ for each $i \in {\mathbb {Z}}_{p-1}$ and each positive integer j. The plan is to choose the factorizations in this order. So for example the ordering of the first $p-1$ near factorizations is $F_{0}, F_{1}, \ldots , F_{(p-3)/2}, F_{(p-3)/2}, F_{(p-5)/2}, \ldots , F_{0}$. This appears to be an unusual ordering, but is essential for the reason that is explained below. Form a sequence $T= (T_{0}, \ldots , T_{p(n + 2\lfloor n/(2p-4) \rfloor + 1)/2 - 1})$ of almost parallel classes of $K_{p}$, where for $0 \le i \le p-1$ and $0\le k \le (n+ \lceil n/(p-2) \rceil )/2 -1$, $T_{i+kp}$ is the almost parallel class (a near 1-factor or a near 2-factor) in $F_{k}$ with deficiency i (it may help to note that exactly $p(2\lfloor n/(2p-4) \rfloor + 1)$ of the almost parallel classes in T are near 1-factors, the rest being near 2-factors). In this case, it is important to note that the ordering in which the factorizations are used is chosen to ensure that each color class is regular of odd degree and balanced (a multigraph G is said to be balanced if the multiplicity between any two pairs of vertices differs by at most 1). The role of $F_{0}$ is critical in this regard. Since the factorizations are chosen in the order $F_{0}, F_{1}, \ldots , F_{(p-3)/2}, F_{(p-3)/2}, F_{(p-5)/2}, \ldots , F_{0}$, the critical observations are

• ($*$) if $(X_{0}, \ldots , X_{p-2}) = (F_{0}, F_{1}, \ldots , F_{(p-3)/2}, F_{(p-3)/2}, F_{(p-5)/2}, \ldots , F_{0})$, then for all $v \in {\mathbb {Z}}_{p}$, $\bigcup _{j \in {\mathbb {Z}}_{p-1}}X_{j}(v) = 2K_{p}$, and

• ($**$) for any $i< p-1$ and all $v\in {\mathbb {Z}}_{p}$, $\bigcup _{j \in {\mathbb {Z}}_{i}}X_{j}(v)$ is balanced (since $\bigcup _{j \in {\mathbb {Z}}_{(p-1)/2}}X_{j}(v) = K_{p}$) and regular of odd degree (since $F_{0}$ is the only graph where vertices have odd degree).

For each $i \in {\mathbb {Z}}_{p}$ let G(i) be the subgraph of $n^{2}K_{p}$ induced by the edges in $\bigcup _{k=0}^{(n + 2\lfloor n/(2p-4) \rfloor + 1)/2 - 1}T_{i+kp}$. Color all edges in G(i) with i. To complete this coloring to an np-coloring of $n^{2}K_{p}$, for each $i \in {\mathbb {Z}}_{p}$ and $j \in {\mathbb {Z}}_{np}$, let $G(j) = G(i)$ if $i \equiv j$ (mod p). Then color class i consists of edges in $2\lfloor n/(2p-4) \rfloor + 1$ near 1-factors and $(n - 2\lfloor n/(2p-4) \rfloor - 1)/2$ near 2-factors which all have the same deficiency i for some $i\in V(K_{p})$, and hence each color class is an n-regular subgraph of $n^{2}K_{p}-i$. By ($*$) and ($**$) this np-coloring is fair. By Corollary 2.3 we conclude that there exists a fair holey 1-factorization of K(n, p). $\square$

5 Final Remark

It is worth noting that there is another notion of fairness one could define from the perspective of each color class of K(n, p), requiring that its edges are shared out as evenly as possible among the permitted pairs of parts of K(n, p) (if the edges colored c induce a holey 1-factor with deficiency $V_{i}$, then the permitted pairs of parts are those which do not include $V_{i}$ since vertices in $V_{i}$ are incident with no edges colored i). Theorems 4.1 and 4.2 each guarantee that each color class does satisfy this additional fairness property. To see this, note that in each theorem the $n^{2}$ edges between each pair of parts are colored with k colors, where $k=n(p-1)$ in Theorem 4.1 and $k=n(p-2)$ in Theorem 4.2. So for each color c, the number of edges of color c between vertices in a permitted pair of parts is $\lfloor n^{2}/k \rfloor$ or $\lceil n^{2}/k \rceil$ as required.