Inherited Vertex Coloring of Graphs

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.

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.


  1. Dustin Mixon’s blog post reformulated and generalized the question in a beautiful way.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. How we use related graph-theoretical techniques in artificial intelligence algorithms.
  7. 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.