论文标题
彩虹完美且近乎完美的匹配，完整的图表，边缘颜色为圆形距离
Rainbow Perfect and Near-Perfect Matchings in Complete Graphs with Edges Colored by Circular Distance
论文作者
论文摘要
给定边缘颜色的完整图$ k_n $在$ n $顶点上，一个完美的（分别，几乎完美）匹配$ m $ $ k_n $的$ m $，如果所有边缘都具有不同的颜色，则均匀（分别为奇数）的顶点是彩虹。在本文中，我们考虑了圆形距离的$ k_n $的边缘着色，我们用$ k^{\ bullet} _n $表示所得完整的图。我们表明，当$ k^{\ bullet} _n $具有均匀数量的顶点时，它包含彩虹完美的匹配，并且仅当$ n = 8k $或$ n = 8k+2 $时，其中$ k $是一个非负整数。对于奇数的顶点，柯克曼匹配是$ k^{\ bullet} _n $的彩虹接近完美的匹配。但是，现实世界中的应用有时需要多个彩虹接近完美的比赛。我们提出了一种使用递归算法在$ k^{\ bullet} _n $中生成多个彩虹接近完美匹配的方法。
Given an edge-colored complete graph $K_n$ on $n$ vertices, a perfect (respectively, near-perfect) matching $M$ in $K_n$ with an even (respectively, odd) number of vertices is rainbow if all edges have distinct colors. In this paper, we consider an edge coloring of $K_n$ by circular distance, and we denote the resulting complete graph by $K^{\bullet}_n$. We show that when $K^{\bullet}_n$ has an even number of vertices, it contains a rainbow perfect matching if and only if $n=8k$ or $n=8k+2$, where $k$ is a nonnegative integer. In the case of an odd number of vertices, Kirkman matching is known to be a rainbow near-perfect matching in $K^{\bullet}_n$. However, real-world applications sometimes require multiple rainbow near-perfect matchings. We propose a method for using a recursive algorithm to generate multiple rainbow near-perfect matchings in $K^{\bullet}_n$.
