This question is a sequel of my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked question follows from
Claim 2. Let $G$ be a graph on $n$ vertices whose edges are colored into $n-k$ colors such that each color class is spanning. Then $G$ has a rainbow perfect matching.
Recall that a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Although this subject is well-studied I failed to find an answer, for which biggest $k=k(n)$ Claim 2 holds.
The upper bounds for $k(n)$
The case of the large $k(n)$ looks too good to be true. In fact, since a perfect matching for $G$ has $n'=n/2$ edges, Claim 2 can hold only when $k\le n'$. Moreover, Lo suggested the proof of the following
Proposition 3. $k(n)\le n’-2$, if $n’$ is even and $k(n)\le n’-1$, if $n’$ is odd.
Proof. Let $v_1,\dots, v_{n’}, u_1,\dots, u_{n’}$ be the vertices of a graph $G=K_{n}$. Color edges of $G$ as follows. For each $1\le i,j\le n’$ the edge between $v_i$ and $u_j$ has color $i+j \mod n’$ and all remaining edges have color $n’$. If $n’$ is even then it is known that there is no rainbow matching of size $n'$ consisting of edges which have colors from $0$ to $n’-1$. If $n’$ is odd then to assure absence of such matching remove from $G$ all edges of color $0$. Now we can easily check that $G$ has no rainbow perfect matching. $\square$
Neugebauer, Wolff, and R. obtained the following
Proposition 4. $k(n)\le n’-3$, if $n’=\pm 1\pmod 6$.
Proof. Let $V$ and $U$ be a bipartition of vertices of a graph $G=K_n$ such that $|V|=n’+2$ and $|U|=n’-2$. We color edges of $G$ into colors which are elements of the set $V$ as follows. The edges between vertices of $U$ remain uncolored. For each $v\in V$ and $u\in U$ the edge $vu$ has color $v$. Since $n’=\pm 1\pmod 6$, there exists a Steiner triple system $\mathcal S$ with elements of $V$. Thus for each distinct vertices $v,v’\in V$ there exists a unique vertex $v’’\in V$ such that a set $\{v,v’,v’’\}$ is a block of $\mathcal S$. We color the edge $vv’$ of $G$ into the color $v’’$. It is easy to check that each color class of the constructed coloring is spanning.
Suppose for a contradiction that $G$ has a rainbow perfect matching $M$. Since edges between vertices of $U$ are uncolored, $M$ has $|U|=n’-2$ edges between $U$ and $V$ and so exactly two edges $e$ and $e’$ with both endvertices in $V$. Let a set $V’$ consists of these four vertices. Since all colors of $V\setminus V’$ are used to color edges of $M$ incident to vertices of $U$, colors $v$ and $v’$ of the edges $e$ and $e’$, respectively belong to $V’$. It follows that $e=v’v’’$ and $e’=vv’’’$ for some vertices $v’’,v’’’\in V’$. But then the pair $\{v,v’\}$ belongs to two distinct blocks $\{v,v’,v’’\}$ and $\{v,v’,v’’’\}$ of $\mathcal S$, a contradiction. $\square$
The lower bounds for $k(n)$
Proposition 5. $k(n)\ge 1$.
Proof. For $k=1$, Claim 2 follows from a more general conjecture by Li and Wang from 2008, finally proved by Kostochka and Yancey in 2012, and stating that if $H$ is an edge-colored graph such that each vertex of $H$ is incident to edges of at least $\ell$ distinct colors then $H$ has a rainbow matching of size $\lceil \ell/2\rceil$. $\square$
Remark that Li and Wang said that proper edge-colorings of complete graphs show that their conjecture is sharp if true, but I do not know whether we can provide counterexamples with a big number $n-k$ of spanning color classes.
Proposition 6. $k(n)\ge 2$ for $n\le 8$.
Proof. A quick case check shows that Claim 2 holds for $n=6$ and $k=2$. Neugebauer in his bachelor thesis showed using a SAT solver that $k(8)=2$. $\square$
Thanks.
