Importance: High ✭✭✭
 Author(s):
 Subject: Graph Theory
 Keywords:
 Posted by: Mario Krenn on: March 4th, 2019
Conjecture   For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?

Background: This and many related questions are directly inspired from quantum physics, and their solutions would directly contribute to new understanding in quantum physics.

Bi-Colored Graph: A bi-colored weighted graph , on vertices with colors is an undirected, not necessarily simple graph where there is a fixed ordering of the vertices and to each edge there is a complex weight and an ordered pair of (not necessarily different) colors associated with it from the possible colors. We say that an edge is monochromatic if the associated pair of colors are not different, otherwise the edge is bi-chromatic. Moreover, if is an edge incident to the vertices with and the associated ordered pair of colors to is then we say that is colored at and at .

We will be interested in a special coloring of this graph:

Inherited Vertex Coloring: Let be a bi-colored weighted graph and denote a perfect matching in . We associate a coloring of the vertices of G with PM in the natural way: for every vertex there is a single edge that is incident to , let the color of be the color of at . We call this coloring , the inherited vertex coloring (IVC) of the perfect matching PM.

Now we are ready to define how constructive and destructive interference during an experiment is governed by perfect matchings of a bi-colored graph.

Weight of Vertex Coloring: Let be a bi-colored weighted graph. Let be the set of perfect matchings of which have the coloring as their inherited vertex coloring. We define the weight of as Moreover, if =1 we say that the coloring gets unit weight, and if =0 we say that the coloring cancels out.

## Bibliography

* indicates original appearance(s) of problem.