论文标题
边彩图只有单色完美匹配及其与量子物理的连接
Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics
论文作者
论文摘要
Krenn，Gu和Zeilinger启动了PMVALID边缘色的研究，因为它与量子物理学的问题有关。图表被定义为具有PMVALID $ K $ - edge-彩色，如果它承认$ k $ - 边缘色（即带有$ k $ - 彩色的边缘着色），所有完美的匹配都是单色的，并且每个$ K $颜色的颜色类都至少包含一个完美的匹配。 图$ g $，$μ（g）$的匹配索引定义为$ g $的最大值$ k $，$ g $允许pmvalid $ k $ edge-ended-odering。当$ g $具有完美的匹配时，很容易看到$μ（g）\ geq 1 $（由于$ 1 $ 1 $ - edge-the Pmvalid的琐碎）。 Bogdanov观察到，对于所有图表，非同态至$ k_4 $，$μ（g）\ leq 2 $和$μ（k_4）= 3 $。但是，尚不清楚$μ（g）= 1 $和$μ（g）= 2 $的图表的表征。在这项工作中，我们回答了这个问题。使用此表征，我们还提供了一种快速算法来计算图$ g $的$μ（g）$。鉴于我们的工作，现在所有$ k $都完全理解了PMVALID $ K $ - edge色的图表的结构。我们的表征，也对上述量子物理问题有影响。特别是，它将krenn和gu的猜想定为一类图形。
Krenn, Gu and Zeilinger initiated the study of PMValid edge-colourings because of its connection to a problem from quantum physics. A graph is defined to have a PMValid $k$-edge-colouring if it admits a $k$-edge-colouring (i.e. an edge colouring with $k$-colours) with the property that all perfect matchings are monochromatic and each of the $k$ colour classes contain at least one perfect matching. The matching index of a graph $G$, $μ(G)$ is defined as the maximum value of $k$ for which $G$ admits a PMValid $k$-edge-colouring. It is easy to see that $μ(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$, $μ(G)\leq 2$ and $μ(K_4)=3$. However, the characterisation of graphs for which $μ(G)=1$ and $μ(G)=2$ is not known. In this work, we answer this question. Using this characterisation, we also give a fast algorithm to compute $μ(G)$ of a graph $G$. In view of our work, the structure of PMValid $k$-edge-colourable graphs is now fully understood for all $k$. Our characterisation, also has an implication to the aforementioned quantum physics problem. In particular, it settles a conjecture of Krenn and Gu for a sub-class of graphs.
