Graphs with only disjoint perfect matchings, with coloring

Question

The following purely graph-theoretic question is motivated by quantum mechanics.

Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be monochromatic or bi-chromatic. The later means that the two endpoints of an edge are allowed to have different colors.

We will be interested in perfect matchings of bi-colored graphs. If $G$ is a bi-colored graph and PM is a perfect matching in $G$ then we can associate a coloring of the vertices of $G$ to the matching PM in the natural way: every vertex gets the color of the edge of PM that is incident to said edge. (Note that a red-blue bi-chromatic edge of PM results in one endpoint of this edge being colored red but the other one blue.) We call these associated (inherited) colorings the inherited vertex coloring (IVC) of the perfect matching PM.

Question: Is there a bi-colored graph with $|V|>4$ with the following properties:

1. For all three colors (red, green, blue) there is at least one perfect matching that has a monochromatic IVC.

2. For every non-monochromatic vertex coloring $c$, there is either no perfect matching of $G$ that has its IVC equal to $c$, or there are at least two such perfect matchings.

• The special case for graphs with no non-monochromatic IVC has been solved by Ilya Bogdanov.
• The connection to quantum mechanics is described in this article (where I also cite Ilya's solution at MO).

---

Example of Inherited Vertex Coloring:

Here I show an example Graph with 8 vertices, with monochromatic and bichromatic edges. It has 7 perfect matchings. For each of the three colors red, blue and green, there is exactly one perfect matching with a monochromatic IVC (PM1-3).

For the coloring ($g$=green, $b$=blue, $r$=red) $c=ggggbbbb$, there are two PMs with that IVC (PM4 and PM6) - this is property 2.

However, for the non-monochromatic vertex coloring $c=bbbbgggg$ and $c=rgggbrrr$, there is exactly one such perfect matching with this IVC - this the graph $G(V,E)$ does not have the required property.

Answer 1

Look at the strong product of an even complete graph with an even cycle, $G=K_{2n}\boxtimes C_{2m}$. We can give an edge coloring to this graph such that any vertex coloring is either not inherited from a perfect matching, or it is inherited by exponentially many matchings, and all monochromatic vertex colorings are induced from some perfect matching.

We can denote the vertices by pairs $(x,y)$ with $x\in \{1,2,\dots,2n\}$ and $y\in \mathbb Z/2m\mathbb Z$, so that we have edges $(x_1,y_1)\sim(x_2,y_2)$ iff $y_1-y_2\in \{-1,0,1\}$. We will pick the coloring of the edges as follows: the blue edges are all edges of the form $\left((x_1,y),(x_2,y)\right)$, the green edges are all edges of the form $\left((x_1,2y)(x_2,2y+1)\right)$, and the red edges are all edges of the form $\left((x_1,2y)(x_2,2y-1)\right)$.

For a given coloring, $C$, of the vertices of $G$ we let $C(b,y), C(g,y), C(r,y)$ denote the number of values of $x$ for which $(x,y)$ is colored blue, green, or red, respectively. It is easy to prove that $C$ is the inherited coloring of a perfect matching in $G$ iff

• $C(g,2y)=C(g,2y+1)$ for all $y$
• $C(r,2y)=C(r,2y-1)$ for all $y$
• $C(b,y)$ is even for all $y$

in particular this is satisfied for all monochromatic colorings. Given such a coloring $C$, the number of perfect matchings that induce it is given by $$\prod_{y=1}^mC(g,2y)!C(r,2y)!\prod_{y=1}^{2m}(C(b,y)-1)!!$$ which is not only greater than 1, but grows like $e^{O(nm\log n)}$.