2
$\begingroup$

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&&&&X\end{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&X\end{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&7\end{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.

Improve this question
$\endgroup$
10
  • $\begingroup$ I don't quite understand your description of the pre-coloring. Are there any restrictions on how you colour? For general $n$, shouldn't it be the last $n/2$ subdiagonals?Transversal also has a concise meaning in latin squares, but I don't think this is what you mean by transversal. $\endgroup$
    – Florian Lehner
    Jul 24, 2020 at 8:48
  • $\begingroup$ @FlorianLehner edited the post, thanks $\endgroup$
    – vidyarthi
    Jul 24, 2020 at 9:53
  • 2
    $\begingroup$ At this point, it is still unclear to me, what "follow the same pattern" is. It might help if you clarify what exactly is the precouloring that you are interested in. $\endgroup$
    – Moritz Firsching
    Jul 24, 2020 at 12:07
  • $\begingroup$ @MoritzFirsching edited the post. See now for the pattern I follow $\endgroup$
    – vidyarthi
    Jul 24, 2020 at 12:28
  • 1
    $\begingroup$ I updated my question to show non-uniqueness for the case $n=10$, using the clarified definition of the precoloring, I hope I understood correctly now. $\endgroup$
    – Moritz Firsching
    Jul 25, 2020 at 11:21

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I didnt quite get your last paragraph. You meant we can have at most $k$ in a single row? And then what is the permutation you are talking about? In the case $n=8$, as shown in the answer by Moritz, it is unique it seems $\endgroup$
    – vidyarthi
    Jul 24, 2020 at 11:53
  • 1
    $\begingroup$ Since you have updated the question and are now asking about one specific precolouring, this answer does not fit the question anymore. The pre-colouring I had in mind for the second part was $1,2,\dots,k$ in the first row, $1,2,\dots, k-1$ in the second row, $1,2,\dots, k-2$ in the third row etc. If this can be extended to a full colouring (which I think should be possible), then there is more than one way to do it (e.g. swap the roles of $k+1$ and $k+2$). $\endgroup$
    – Florian Lehner
    Jul 24, 2020 at 15:47
  • $\begingroup$ why do you think the extension is possible for the kind of coloring I give? $\endgroup$
    – vidyarthi
    Jul 25, 2020 at 9:23
  • $\begingroup$ I have no idea whether it is or isn't possible for your specific precolouring, all I'm saying is that my examples don't fit your pattern. $\endgroup$
    – Florian Lehner
    Jul 25, 2020 at 11:06
1
$\begingroup$

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.

Colored C_8

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 $n\geq 8$ and it is not unique for $n\geq 10$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ thanks, edited the question slightly. My question is, can we do this unique extension for every complete graph of even order?That is given the last $k$ subdiagonals, can we always extend the coloring to the whole graph? $\endgroup$
    – vidyarthi
    Jul 24, 2020 at 9:55
  • $\begingroup$ yes, thanks for the case $n=10$, but is there a formal proof for the possibility in every case, because the general problem of precoloring extension is NP-complete. So, I think in this case it is in P. Is it true? Would the uniqueness depend on the choice of the fixed colors? $\endgroup$
    – vidyarthi
    Jul 24, 2020 at 10:22
  • $\begingroup$ So many questions, but I think they can all be answered. For existence of a solution for every n, just take a coloring for all edges (which can always be done with n-1 colors) and forgot all but the $k$ outer diagonals as a precoloring. This can then clearly be extended. to a full coloring again. Uniqueness fails for n=10 already and it might not be too hard to construct more than one coloring for every larger n. I would expect that the number of extensions to a precoloring depends on the choice of precoloring. Perhaps asked more things as a actual questions and not in a comment.. $\endgroup$
    – Moritz Firsching
    Jul 24, 2020 at 10:33
  • $\begingroup$ But, whether our precoloring sequence of fixed colors would appear in the normal edge coloring is the main question we must ask. See the answer by Florian. Yes, uniqueness would not be true, but even completion is also not true, as shown by Florian. But, given the colors having some intersection of colors between any two rows would warrant a completion is my view. $\endgroup$
    – vidyarthi
    Jul 24, 2020 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.