Monochromatic vertex colorings inherited from Perfect Matchings

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $V=\{v_1,\ldots,v_n\}$ be ordered. A bi-colored weighted graph is a finite loopless undirected multigraph on $V$ with a complex weight $w_e$ and an ordered color pair $(c_1(e),c_2(e))\in\{1,\ldots,d\}^2$ on each edge $e=v_iv_j$, $i<j$; its colors at $v_i,v_j$ are respectively $c_1(e),c_2(e)$. A perfect matching $M$ selects one incident edge at each vertex, giving an inherited coloring $c_M(v)$ from that endpoint's edge color. For any coloring $c:V\to\{1,\ldots,d\}$, put \[W(c)=\sum_{M:c_M=c}\prod_{e\in M}w_e,\] with an empty sum equal to zero.

Statement recorded in the supplied source.

Determine all positive integers $n,d$ for which such a graph exists with \[W(c)=\begin{cases}1,&c\text{ is constant},\\0,&c\text{ is nonconstant}.\end{cases}\] Thus each of the $d$ monochromatic inherited vertex colorings has unit weight and all other colorings cancel. [S2]

Short English statement

For which numbers of vertices and colors can weighted perfect matchings produce exactly the monochromatic colorings, each with weight one?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3139 (OPG-60030). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Monochromatic vertex colorings inherited from Perfect Matchings, original node 60030, statement and mathematical discussion. https://www.openproblemgarden.org/op/monochromatic_vertex_colorings_inherited_from_perfect_matchings.