主题
Search

边着色数

图 G 的边着色数，有时也称为色指数，是为图 G 的每条边着色所需的最少颜色数，使得没有两条在同一顶点上关联的边具有相同的颜色。换句话说，它是最小边着色中不同颜色的数量。

图的边着色数必须至少为 Delta，即图的最大顶点度 (Skiena 1990, p. 216)。然而，Vizing (1964) 和 Gupta (1966) 表明，任何图都可以用最多 Delta+1 种颜色进行边着色。因此，图精确地分为两类：边着色数等于 Delta 的图（1 类图）和边着色数等于 Delta+1 的图（2 类图）。

根据定义，图 G 的边着色数等于线图 L(G) 的（顶点）色数。

图的边着色数的计算在 Wolfram 语言中实现为EdgeChromaticNumber[g]。 许多命名图的预计算边着色数可以使用GraphData[graph,"EdgeChromaticNumber"].

二分图的边着色数是 Delta，因此所有二分图都是 1 类图。

确定图的边着色数是一个 NP 完全问题 (Holyer 1981; Skiena 1990, p. 216)。

另请参阅

色数, 1 类图, 2 类图, 边着色, 最大顶点度, 最小边着色, Snark, Vizing 定理

使用 Wolfram|Alpha 探索

参考文献

Fiorini, S. and Wilson, R. 图的边着色. Pittman, 1977.Gupta, R. P. "图的色指数和度." Not. Amer. Math. Soc. 13, 719, 1966.Holyer, I. "边着色的 NP 完全性." SIAM J. Comput. 10, 718-720, 1981.Nemhauser, G. L. and Park, S. "边着色的多面体方法." Operations Res. Lett. 10, 315-322, 1991.Skiena, S. "边着色." §5.5.4 in 用 Mathematica 实现离散数学：组合数学和图论. Reading, MA: Addison-Wesley, p. 216, 1990.Vizing, V. G. "关于 p-图的色类的估计" [俄语]. Diskret. Analiz 3, 23-30, 1964.

在 Wolfram|Alpha 上被引用

边着色数

请引用为

Weisstein, Eric W. "边着色数." 来自 MathWorld--Wolfram 网络资源. https://mathworld.net.cn/EdgeChromaticNumber.html

主题分类