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$) 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.