10
$\begingroup$

In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-colored graph:

Definition: (inherited vertex coloring $c$ of $PM$) Let $G(V,E)$ be a graph who's edges $e \in E$ are colored. For every vertex $v_i$ in an edge-colored graph $G$, there is a single edge $e(v_i) \in PM$ that is incident to $v_i$, let the color of $v_i$ be the color of $e(v_i)$.

A graph with $n$ perfect matchings has $n$ (not necessarily different) inherited vertex colorings $c$; let's call the set of all inherited vertex colors $\mathcal{C}$. One could now ask about properties of $\mathcal{C}$. For example, Ilya Bogdanov has shown that if all $c \in \mathcal{C}$ are monochromatic, then $|\mathcal{C}|\leq3$, and if $|\mathcal{C}|=3$, then $|c|=4$.

It seems to me that this notion of vertex coloring is so natural, that it makes me wonder the following:

Question: Has this (or similar) notions of vertex colorings been studied before? Isit be known under other names, maybe not under the name coloring but labeling? Is it related to other properties studied in graph theory?

An example:

enter image description here A graph with 6 vertices. The three perfect matchings lead to three inherited vertex colorings.

One can asked other, more general questions about it (with weighted, bi-colored graphs), but here this the most natural and simple form of coloring i believe.

Added (24.08.2019): As I consider this property important for quantum physics, I have announced an award for the best paper on this within the next two years, and another award for the solution of a certain question.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Mario, the setting is not clear. Are you given a graph G PLUS a coloring of the edges (that can be arbitrary), and then for every perfect matching you color the vertices according to the color of the edges they belong to? $\endgroup$
    – Gil Kalai
    Feb 14, 2020 at 6:41
  • $\begingroup$ yes, you described it perfectly. i give G (G involves set of vertices, edges and corresponding edge colors). the vertices get the colorings in the way you describe. in general, i can start asking questions about existance of a graph G, which produce specific vertex coloring. such questions naturally follow from quantum mechanical questions about creatability of certain quantum states. $\endgroup$
    – Mario Krenn
    Feb 15, 2020 at 10:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.