5
$\begingroup$

It seems like the answer to this question ought to be well-known, or at least some conjectures made if it's unsolved, but my searches so far have come up empty.

In how many ways may we color the edges of a labeled $K_n$, using the minimal number of colors, so that no vertex is incident to two edges with the same color?

For $K_2$, there is obviously 1:

K_2 colorings

For $K_3$, we have 6:

K_3 colorings

And for $K_4$, also 6:

K_4 colorings

This question is related to Number of different minimal proper edge colorings of $K_n$, which currently has no answers and does not assume that the vertices are labeled.

$\endgroup$
4
$\begingroup$

Counting edge-colorings of $K_n$ is closely related to counting symmetric Latin squares. In fact, I'll show that if $S_n$ denotes the number of symmetric $n \times n$ Latin squares (symmetric matrices with entries in the set $\{1,2,\dots,n-1\}$ where each row and each column includes every value exactly once) then the number of minimal proper edge-colorings of $K_n$ is equal to $S_{n-1}$ when $n$ is even and $S_n$ when $n$ is odd.

This paper shows that $S_n$, the number of symmetric $n \times n$ Latin squares, satisfies $$S_n \sim n! \cdot n^{\frac38 n^2}$$ for odd $n$, which gives at least an asymptotic answer to your question as well.

When $n$ is odd, a minimal proper edge-coloring of $K_n$ uses $n$ colors, each appearing on $\frac{n-1}{2}$ edges, and therefore at each vertex one color is left out. We define a map from these edge-colorings to $n \times n$ symmetric Latin squares as follows:

  • Assign values $1, 2, \dots, n$ to the colors.
  • For $1 \le i < j \le n$, put the color of the edge between $i$ and $j$ in the $(i,j)^{\text{th}}$ entry of the Latin square.
  • For $1 \le i \le n$, put the color not appearing at vertex $i$ in the $(i,i)^{\text{th}}$ entry of the Latin square.

The result is a symmetric Latin square, and reversing this process always produces a minimal proper edge-coloring. So the number of colorings is $S_n$.

For even $n$, we may simply reduce to the $(n-1)$-vertex case by leaving out one vertex. The resulting coloring is always a minimal proper edge-coloring of $K_{n-1}$, and we can always infer what the colors on the deleted edges must have been, and reverse this process. So the number of colorings is $S_{n-1}$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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