In 2018 Mario Krenn posed this originated from recent advances in quantum physics question on a maximum number of colors of a monochromatic graph with $n$ vertices. Despite very intensive Krenn’s promotion and our efforts, the question is answered only in special cases. For instance, the case of $n=4$ vertices was solved by kevin by means of Groebner bases. But, as far as I know, already for $n=6$ the answer is unknown and even a description of two-colored answers seems to be a too hard problem.
So our present question is
What is the maximum number $C(n)$ of colors of a monochrome-edge-only monochromatic graph on $n$ vertices?
Since all graph edges are monochromatic, the weight of a vertex coloring splits into the product of weights of its monochrome subsets, see below. This reduces the general problem and we were able to obtain upper bounds on $C(n)$. As far as I know, the present best bounds are $C(4)=3$, $C(6)=2$, $2\le C(8)\le 3$, and $2\le C(n)\le n-3$ for all even $n\ge 10$.
But since it is conjectured that $C(n)=2$ for each even $n\ge 6$, we are trying to improve these bounds using that a monochrome-edge-only monochromatic graph with the vertex set $V$ and $C$ colors exists iff there exists a family $\mathbb S$ (induced by the graph) of $C$ weight supports on $V$ which is incompatible, that is there is no partition of $V$ into at least two sets belonging to distinct members of $\mathbb S$.
Example. Given a perfect matching $M$ on the set $V$ then for any edge $e$ of $K_n$ we can put $w(e)=1$, if $e$ belongs to $M$, and $w(e)=0$, otherwise. It is easy to see that in this case the support $\mathcal S$ consists of all nonempty unions of edges of $M$. We denote this support as $\widehat M$. It is easy to check that if $n\ge 4$ then a cycle on the set $V$ can be split into two perfect matchings $M_1$ and $M_2$, consisting of the odd-numbered and even-numbered edges of the cycle, respectively, and then $\{\widehat{M_1},\widehat{M_2}\}$ is an incompatible family of supports on $V$. It follows that $C(n)\ge 2$. Moreover, incompatible families of supports are related to Kotzig’s perfect 1-factorization conjecture. Namely, if $\mathcal P$ is a perfect 1-factorization of a complete graph with the vertex set $V$ then $\widehat{\mathcal P}=\{\widehat M: M\in{\mathcal P}\}$ is a family of supports on $V$ such that there is no partition of $V$ into $\underline{\mbox{two}}$ sets belonging to distinct members of $\widehat{\mathcal P}$. Unfortunately, Bogdanov’s answer implies that if $n>4$ then there are no perfect matchings $M_1$, $M_2$, and $M_3$ on $V$ such that the family $\{\widehat{M_1},\widehat{M_2},\widehat{M_3}\}$ is incompatible.
Our approach to bound $C(n)$ is to obtain combinatorial conditions on supports and then use them to show that there are no big incompatible families of supports. We are going to use SAT solvers for small $n$ for this purpose. But for big $n$ we need help to improve our present bounds, which are loose. For instance, already the first condition from the linked question provides an upper bound, which is close to the best known.
Proposition. $C(n)\le n-1$ for each even $n\ge 4$.
Proof. Let $\mathbb S$ be an incompatible family of $C(n)$ supports on a set $V$. Fix an arbitrary vertex $v\in V$. By Condition 1, for each support $\mathcal S\in\mathbb S$ there exists a vertex $u(\mathcal S)\in V$ such that both sets $\{v,u(\mathcal S)\}$ and $U\setminus\{v,u(\mathcal S)\}$ belong to $\mathcal S$. Since the family $\mathbb S$ is incompatible, the map $u:\mathbb S\to V\setminus\{v\}$ is injective, so $C(n)=|\mathbb S|\le | V\setminus\{v\}|=n-1$. $\square$
Note also that the refined case analysis based on Condition 1 also shows that $C(6)=2$. On the other hand, for each positive $n$ divisible by $4$ there exists an incompatible family of three families of non-empty even-size subsets of $V$, satisfying Condition 1, see Proposition here. But this family is excluded by Condition 2.
Thanks.
