The edge precoloring extension problem for complete graphs

Question

Consider coloring the edges of a complete graph on even order. This can be seen as the completion of an order $n$ symmetric Latin square except the leading diagonal. My question pertains to whether we can always complete the edge  coloring in $n-1$ colors  given a certain set of colors? The number of colors I fix is exactly equal to $frac{(k)(k+2)}{2}$, where $k=frac{n}{2}$ and form $4$ distinct consecutive  last four subdiagonals (and, by symmetry, superdiagonals) in the partial Latin square.
For example, in the case of $K_8$, I fix the following colors:
begin{bmatrix}X&&&&1&3&7&4\&X&&&&2&4&1\&&X&&&&3&5\&&&X&&&&6\1&&&&X&&&\3&2&&&&X&&\7&4&3&&&&X&\4&1&5&6&&&&Xend{bmatrix}
A completion to a proper edge coloring in this case would be:
begin{bmatrix}X&5&6&2&1&3&7&4\5&X&7&3&6&2&4&1\6&7&X&4&2&1&3&5\2&3&4&X&7&5&1&6\1&6&2&7&X&4&5&3\3&2&1&5&4&X&6&7\7&4&3&1&5&6&X&2\4&1&5&6&3&7&2&Xend{bmatrix}
Can the above be always done if the colors I fix follow the same pattern for all even order complete graphs? Note that the pattern followed in the precoloring consists of two portions-
i) the last $k-1$ subdiagonals are actually taken from a canonical $n$-edge coloring of the complete graph on $n-1$ vertices, where $n$ is even. By canonical, I mean the commutative idempotent 'anti-circulant' latin square. Like in the example above, the canonical coloring of the complete graph on $7$ vertices is
begin{bmatrix}1&5&2&6&3&7&4\5&2&6&3&7&4&1\2&6&3&7&4&1&5\6&3&7&4&1&5&2\3&7&4&1&5&2&6\7&4&1&5&2&6&3\4&1&5&2&6&3&7end{bmatrix}
ii)The $k$-th subdiagonal just consists of entries in the pattern $1-2-3-$ so on and takes into account the previous entries to create an appropriate entry. Like in the example above the last diagonal I took was $1-2-3-6$. It could also have been $1-2-3-7$.
And, if the completion exists, would the completion be unique? Any hints? Thanks beforehand.

Florian Lehner · Answer

Assuming that you mean to precolour $k$ subdiagonals and have no further constraints on the precolouring, the answer to both of your questions is no.
For every $n$ there is a precolouring which cannot be extended: choose colours $1, dots n/2$ in the first row and colours $n/2+1, dots, n-1$ in the second row (and thus the second column). Then there is no valid colour for the entry in the first row/second column, so we cannot complete the colouring.
If we can complete the colouring, then the completion is not necessarily unique: note that we can always give a valid precolouring only using colours $1 dots k$. Thus in any completion of this precolouring we can permute the colours $k+1, dots, n-1$ to obtain a different completion.

Moritz Firsching · Answer

For the case $n=8$, with the precoloring you describe the completion you give is indeed unique. I checked by writing the corresponding boolean program and let a solver enumerate all solutions: there is only one.

For the case $n=10$, consider the pre-colored $K_{10}$
$$left(begin{array}{rrrrrrrrrr}
X &   &   &   &   & 1 & 8 & 4 & 9 & 5 \
  & X &   &   &   &   & 2 & 9 & 5 & 1 \
  &   & X &   &   &   &   & 3 & 1 & 6 \
  &   &   & X &   &   &   &   & 4 & 2 \
  &   &   &   & X &   &   &   &   & 7 \
1 &   &   &   &   & X &   &   &   &   \
8 & 2 &   &   &   &   & X &   &   &   \
4 & 9 & 3 &   &   &   &   & X &   &   \
9 & 5 & 1 & 4 &   &   &   &   & X &   \
5 & 1 & 6 & 2 & 7 &   &   &   &   & X
end{array}right)$$
This can be completed in $77$ ways, for example
$$left(begin{array}{rrrrrrrrrr}
X & 6 & 7 & 3 & 2 & 1 & 8 & 4 & 9 & 5 \
6 & X & 8 & 7 & 3 & 4 & 2 & 9 & 5 & 1 \
7 & 8 & X & 5 & 4 & 2 & 9 & 3 & 1 & 6 \
3 & 7 & 5 & X & 9 & 8 & 6 & 1 & 4 & 2 \
2 & 3 & 4 & 9 & X & 5 & 1 & 6 & 8 & 7 \
1 & 4 & 2 & 8 & 5 & X & 3 & 7 & 6 & 9 \
8 & 2 & 9 & 6 & 1 & 3 & X & 5 & 7 & 4 \
4 & 9 & 3 & 1 & 6 & 7 & 5 & X & 2 & 8 \
9 & 5 & 1 & 4 & 8 & 6 & 7 & 2 & X & 3 \
5 & 1 & 6 & 2 & 7 & 9 & 4 & 8 & 3 & X
end{array}right)
$$ or
$$left(begin{array}{rrrrrrrrrr}
X & 7 & 2 & 6 & 3 & 1 & 8 & 4 & 9 & 5 \
7 & X & 8 & 3 & 4 & 6 & 2 & 9 & 5 & 1 \
2 & 8 & X & 5 & 9 & 4 & 7 & 3 & 1 & 6 \
6 & 3 & 5 & X & 8 & 7 & 9 & 1 & 4 & 2 \
3 & 4 & 9 & 8 & X & 5 & 1 & 6 & 2 & 7 \
1 & 6 & 4 & 7 & 5 & X & 3 & 2 & 8 & 9 \
8 & 2 & 7 & 9 & 1 & 3 & X & 5 & 6 & 4 \
4 & 9 & 3 & 1 & 6 & 2 & 5 & X & 7 & 8 \
9 & 5 & 1 & 4 & 2 & 8 & 6 & 7 & X & 3 \
5 & 1 & 6 & 2 & 7 & 9 & 4 & 8 & 3 & X
end{array}right)$$
This answers your question about uniqueness.
So it looks very plausible to me, that the completion can always be done for $ngeq 8$ and it is not unique for $ngeq 10$.

The edge precoloring extension problem for complete graphs

2 Answers

Add your own answers!

Ask a Question