Edge-Coloured Graphs with only Monochromatic Perfect Matchings and Their Connection to Quantum Physics

Abstract

Krenn, Gu, and Zeilinger initiated the study of PMValid edge-colourings because of their connection to a problem from quantum physics. A graph is defined to have a PMValid $k$-edge-colouring if it admits an edge colouring (not necessarily proper) with $k$ colours, with the property that all perfect matchings are monochromatic and each of the $k$ colour classes contains at least one perfect matching. The matching index of a graph $G$, $\mu(G)$, is defined as the maximum value of $k$ for which $G$ admits a PMValid $k$-edge-colouring. It is easy to see that $\mu(G)\geq 1$ if and only if $G$ has a perfect matching (due to the trivial $1$-edge-colouring, which is PMValid). Bogdanov observed that for all graphs non-isomorphic to $K_4$, $\mu(G)\leq 2$; $\mu(K_4)=3$. However, the characterization of graphs for which $\mu(G)=1$ and $\mu(G)=2$ was not known. In this work, we answer this question. Using this characterization, we also give a fast algorithm to compute the value of $\mu(G)$ for a graph $G$. In view of our work, the structure of PMValid $k$-edge-colourable graphs is now fully understood for all $k$. Our characterization also has implications for the aforementioned quantum physics problem. In particular, it settles a conjecture of Krenn and Gu for a subclass of graphs.