We discovered a new form of vertex colors of graphs (inherited directly form edge-colorings of perfect matchings) in the study of quantum physics questions.

Several new pure graph theoretical questions emerged, and I believe that their answer could lead to exciting insights on the potential of resources of quantum interference.

I have described the question in detail in a youtube video, mathoverflow question, and a contribution to the proceedings of 2nd Croatian Combinatorial Days (arXiv version), and was described in detail by Dustin Mixon.

## 1) 3.000 Euro Reward

We offer a **3.000 Euro reward** for the first solution of our conjecture (either proof or counterexample) (mathoverflow question, Dustin Mixon’s blog, youtube (see Clarification below video), Question1 here):

**Update January 2021: **Not only solutions to Question2, but also counter-examples to the conjecture will be awarded the reward.

The solution has to appear in a respected, peer-reviewed journal (or for counterexamples, there needs to be a way to confirm them, for instance via software). The problem can be concisely formulated in the language of graph theory and combinatorial equation systems.

## 2) 1.000 Euro Best-Paper Award

We offer a** 1.000 Euro award for the best paper** which investigates inherited vertex colors of graphs, derives new results or connections. The deadline will be March 2023.

**Best-Paper Award 2022:**

L. Sunil Chandran, Rishikesh Gajjala: Perfect Matchings and Quantum Physics: Progress on Krenn’s Conjecture [youtube]*for the confirmation of the conjecture for large classes of simple graphs, as well as the introduction and disprove of a natural generalisation.*

Rules: The paper needs to be correct (peer-reviewed in a serious journal or proceedings, and/or I need to able to understand the results) and the results should be non-trivial/obvious. At the deadline, i will ask for recommendations by experts. In case of two interesting papers, the award could be splitted.

## Known special cases

- [
**April 2017**]: For real, positive weights, it follows from Bogdanov’s lemma that monochromatic weighted graphs cannot exist for (n=4,d>3) and (n>=6,d>2). - [
**September 2021**]: For monochromatic edges, we proved using SAT solvers that (n=6,d>=3) and (n=8, d>=4) monochromatic weighted graphs don’t exist. - [
**February 2022**]: For monochromatic edges, without multi-edges, a monochromatic graph cannot exist for d=n-2 (even n>=6), due to Chandran & Gajjala.

## References

- Dustin Mixon’s blog post reformulated and generalized the question in a beautiful way.
- Questions on the Structure of Perfect Matchings inspired by Quantum Physics – here, together with my colleages Xuemei Gu and Daniel Soltesz, we formalize the ideas of bi-chromatic, edge-colored weighted graph, and the concept of inherited vertex coloring, together with several examples, and a number of noteworthy open question on the topic.
- My mathoverflow question Vertex Coloring inherited from Perfect Matchings (motivated by Quantum Physics) where I explain the idea of inherited vertex coloring and particularily the question for the reward more compactly.
- My mathoverflow question Has this notion of vertex-coloring of graphs been studied? where I explain the concept of bi-chromatic edge-colored graphs and inherited vertex coloring more compactly.
- A post by Ilya Bogdanov, which answeres the question of the reward for the special case of graphs with all weights being real and positive.
- How we use related graph-theoretical techniques in artificial intelligence algorithms.
- Using SAT solvers, we proof a few special cases of the conjecture (specifically for graphs with only monochromatic edges).

## Questions and Comments

For any questions and clarifications, please send me an e-Mail.