2022-08

Vizing 定理 对于简单图 $G$: $$\chi'(G) \le \Delta (G) + 1$$ 其中 $\chi'(G)$ 为图 $G$ 的边色数，即最少使用多少颜色可以为 $G$ 的边染色，使得相邻边彼此颜色不同。$\Delta (G)$ 是图的最大点度数。 二分图 Vizing 定理 特别的对于二分图我们有 $$\chi'(G) = \Delta (G) $$ 我们可以构 …