主题
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 定理

使用 探索

参考文献

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.

在 上被引用

边着色数

请引用为

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

主题分类