主題
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.tw/EdgeChromaticNumber.html

主題分類