55、图论中的彩虹连接与超图中的近似完美匹配问题研究

图论中的彩虹连接与超图中的近似完美匹配问题研究

1. 图的彩虹连接问题

在图论中，彩虹连接是一个有趣的概念。一个边着色图 $G$ 若任意两个顶点都由边颜色不同的路径相连，则称该图是彩虹连通的。连通图 $G$ 的彩虹连接数 $rc(G)$ 是使 $G$ 彩虹连通所需的最少颜色数。

• 基本性质

  • 若图 $G$ 有 $n$ 个顶点，则 $rc(G) \leq n - 1$。因为可以给图 $G$ 的生成树的边着不同颜色，其余边着已使用过的颜色。
  • $rc(G) = 1$ 当且仅当 $G$ 是完全图；$rc(G) = n - 1$ 当且仅当 $G$ 是树；对于有 $k \geq 3$ 个顶点的环，其彩虹连接数为 $\lceil\frac{k}{2}\rceil$。
  • 同时，$rc(G) \geq diam(G)$，其中 $diam(G)$ 表示图 $G$ 的直径。

• 已有定理与猜想

  • 定理 1 ：若 $G$ 是有 $n$ 个顶点且最小度 $\delta(G) \geq 3$ 的连通图，则 $rc(G) < \frac{5n}{6}$。
  • 猜想 1 ：若 $G$ 是有 $n$ 个顶点且最小度 $\delta(G) \geq 3$ 的连通图，则 $rc(G) < \frac{3n}{4}$。对于 2 - 连通图，此猜想成