主題
Search

色多項式

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

色多項式 pi_G(z) 是一個無向圖 G 的多項式，也表示為 C(G;z) (Biggs 1973, p. 106) 和 P(G,x) (Godsil and Royle 2001, p. 358)，它是一個多項式，編碼了給 G 的頂點著色的不同方式的數量（即使著色僅因顏色排列而異，也算作不同的著色）。對於一個在 G 上有 n 個頂點的圖，它可以用 0 種顏色以 k_0=0 種方式著色，用 1 種顏色以 k_1 種方式著色，...，用 k_n 種方式著色，圖 G 的色多項式被定義為透過 n+1 個點 (0,k_0), (1,k_1), ..., (n,k_n) 的唯一的 n 次拉格朗日插值多項式。在變數 z 中評估色多項式在點 z=1, 2, ..., n 處的值，可以得到 1-著色、2-著色、... 和 n-著色的數量。事實上，在整數 k>n 處評估 pi_G(z) 仍然給出 k-著色的數量。

色多項式在 Bari (1974) 的著作中簡稱為 “chromial”。

圖的色數給出了可以對圖進行著色的最少顏色數，因此它是最小的正整數 z 使得 pi_G(z)>0 (Skiena 1990, p. 211)。

例如，立方圖 Q_3 的 1-、2-、... k-著色 計數分別為 0, 2, 114, 2652, 29660, 198030, 932862, 3440024, ... (OEIS A140986)，由此得到的色多項式為

pi_(Q_3)(z)=z^8-12z^7+66z^6-214z^5+441z^4-572z^3+423z^2-133z.
(1)

在 z=1, 2, ... 處評估 pi_(Q_3)(z)，得到預期的 0, 2, 114, 2652, 29660, 198030, 932862, 3440024, ...。

色多項式的根被稱為色根，不包含色根的區間稱為無色根區間。

圖 g 關於變數 z 的色多項式可以使用 Wolfram 語言來確定，使用方法如下：ChromaticPolynomial[g, x]。許多命名圖的預計算色多項式可以使用以下方法獲得GraphData[graph,"ChromaticPolynomial"][z]。

色多項式對於圖的連通分量是可乘的，因此對於具有連通分量 G_1, G_2, ... 的圖 G，G 本身的色多項式由下式給出：

pi_G=pi_(G_1)pi_(G_2)....
(2)

具有 n 個頂點、m 條邊和 c 個連通分量的森林的色多項式由下式給出：

pi=(-1)^(n-c)x^c(1-x)^m.
(3)

對於具有頂點數 n 和 c 個連通分量的圖，色多項式 pi(x) 與秩多項式 R(x,y) 和 Tutte 多項式 T(x,y) 的關係如下：

pi(x)=x^nR(-x^(-1),-1)
(4)
=(-1)^(n-c)x^cT(1-x,0)
(5)

（擴充套件自 Biggs 1993, p. 106）。平面圖 G 的色多項式與其對偶圖 G^* 的流多項式 C_G^*(u) 的關係如下：

pi_G(x)=xC_(G^*)^*(x).
(6)

色多項式不能用於診斷圖同構，即兩個非同構圖可能共享相同的色多項式。由其色多項式確定的圖稱為色唯一圖；共享相同色多項式的非同構圖稱為色等價圖。

梯形圖 P_2 square P_n 和 網格圖 P_2 square P_n 的色多項式在 Yadav 等人 (2024) 的論文中被考慮。下表總結了一些簡單圖的色多項式。這裡 (z)_n 是降階乘。

圖色多項式
啞鈴圖((z)_n^2(z-1))/z
書圖 S_(n+1) square P_2(z-1)z(z^2-3z+3)^n
蜈蚣圖(z-1)^(2n-1)z
完全圖 K_n(z)_n
圈圖 C_n(-1)^n(z-1)+(z-1)^n
齒輪圖z[z-2+(3-3z+z^2)^n]
舵圖z[(1-z)^n(z-2)+(z-2)^n(z-1)^n]
梯形圖 P_2 square P_n(z-1)z(z^2-3z+3)^(n-1)
梯子橫檔圖 nP_2z^n(z-1)^n
莫比烏斯梯子 M_n-1+(1-z)^n-(3-z)^n+(-(1-z)^n+(3-z)^n)z+(3+(-3+z)z)^n
平底鍋圖(z-1)^(n+1)+(-1)^n(z-1)^2
路徑圖 P_nz(z-1)^(n-1)
稜柱圖 Y_n1+[z(z-3)+3]^n+z[(1-z)^n+(3-z)^n+z-3]-(1-z)^n-(3-z)^n
星圖 S_nz(z-1)^(n-1)
太陽圖(z)_n(z-2)^n
日射圖 C_n circledot K_1(z-1)^(2n)-(1-z)^(n-1)
三角形蜂巢車圖product_(k=1)^(n)[(z)_k]^n
網圖z[(1-z)^n+(3-z)^n+z-3](z-1)^n+(z-1)^n-[-(z-3)(z-1)]^n-[-(z-1)^2]^n+[(z-1)((z-3)z+3)]^n
輪圖 W_nz[(z-2)^(n-1)-(-1)^n(z-2)]

下表總結了一些簡單圖類的色多項式的遞推關係。

圖階數遞推關係
反稜柱圖4p_n=(z^2-6z+10)p_(n-1)+(z-3)(2z^2-9z+11)p_(n-2)+(z^2-6z+10)(z-2)^2p_(n-3)-(z-2)^4p_(n-4)
啞鈴圖1p_n=(z-n+1)^2p_(n-1)
書圖 S_(n+1) square P_21p_n=(z^2-3z+3)p_(n-1)
蜈蚣圖1p_n=(z-1)^2p_(n-1)
完全圖 K_n1p_n=(z-n+1)p_(n-1)
圈圖 C_n2p_n=(z-2)p_(n-1)+(z-1)p_(n-2)
齒輪圖2p_n=(z^2-3z+4)p_(n-1)-(z^2-3z+3)p_(n-2)
舵圖2p_n=(z-3)(z-1)p_(n-1)+(z-2)(z-1)^2p_(n-2)
梯形圖 P_2 square P_n1p_n=(z^2-3z+3)p_(n-1)
梯子橫檔圖 nP_21p_n=z(z-1)p_(n-1)
莫比烏斯梯子4p_n=(8-5z+z^2)p_(n-1)+(-22+27z-12z^2+2z^3)p_(n-2)+(24-43z+29z^2-9z^3+z^4)p_(n-3)+(-9+21z-18z^2+7z^3-z^4)p_(n-4)
平底鍋圖2p_n=(z-1)p_(n-2)+(z-2)p_(n-1)
路徑圖 P_n1p_n=(z-1)p_(n-1)
稜柱圖 Y_n4p_n=(z^2-5z+8)p_(n-1)+(z-2)(2z^2-8z+11)p_(n-2)+(z^4-9z^3+29z^2-43z+24)p_(n-3)-(z-3)(z-1)(z^2-3z+3)p_(n-4)
星圖 S_n1p_n=(z-1)p_(n-1)
日射圖 C_n circledot K_12p_n=(z-1)(z-2)p_(n-1)+(z-1)^3p_(n-2)
網圖4p_n=p_n=(z^2-5z+8)(z-1)p_(n-1)+(z-2)(2z^2-8z+11)(z-1)^2p_(n-2)+(z^4-9z^3+29z^2-43z+24)(z-1)^3p_(n-3)-(z-3)(z^2-3z+3)(z-1)^5p_(n-4)
輪圖 W_n2p_n=(z-2)p_(n-2)+(z-3)p_(n-1)

非連通圖的色多項式是其連通分量的色多項式的乘積。階數為 n 的圖的色多項式的次數為 n，首項係數為 1，常數項為 0。此外，係數符號交替，且 ((n-1)) 次項的係數為 -m，其中 m 是邊的數量。有趣的是，pi_G(-1) 等於 G 的無環定向的數量 (Stanley 1973)。

除了特殊情況（例如樹），pi_G(z) 的計算在 G 和圖補 G^_ 中邊的最小數量上是指數級的 (Skiena 1990, p. 211)，並且計算圖的色多項式至少是一個 NP 完全問題 (Skiena 1990, pp. 211-212)。

Tutte (1970) 表明，球體的平面三角剖分的色多項式具有一個接近 phi^2=phi+1=2.618033... (OEIS A104457) 的根，其中 phi 是黃金比例。更精確地說，如果 n 是這種圖 G 的圖頂點的數量，那麼

pi_G(phi^2)<=phi^(5-n)
(7)

(Tutte 1970, Le Lionnais 1983)。

Read (1968) 推測，對於任何色多項式

pi(z)=c_nz^n+...+c_1z,
(8)

不存在 1<=p<=q<=r<=n 使得 |c_p|>|c_q| 且 |c_q|<|c_r| (Skiena 1990, p. 221)。

另請參閱

色區間, 色不變數, 色數, 色根, 色等價圖, 色唯一圖, 流多項式, k-著色, k-色圖, k-可著色圖, Q-色多項式, 秩多項式, Sigma 多項式, Tutte 多項式, 頂點著色

使用 探索

參考文獻

Bari, R. A. "Chromatically Equivalent Graphs." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 186-200, 1974.Berman, G. and Tutte, W. T. "The Golden Root of a Chromatic Polynomial." J. Combin. Th. 6, 301-302, 1969.Biggs, N. L. "Chromatic Polynomials and Spanning Trees." Ch. 14 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 106-111, 1993.Birkhoff, G. D. "A Determinant Formula for the Number of Ways of Coloring a Map." Ann. Math. 14, 42-46, 1912.Birkhoff, G. D. and Lewis, D. C. "Chromatic Polynomials." Trans. Amer. Math. Soc. 60, 355-451, 1946.Chvátal, V. "A Note on Coefficients of Chromatic Polynomials." J. Combin. Th. 9, 95-96, 1970.Dong, F. M., Koh, K. M.; and Teo, K. L. Chromatic Polynomials and Chromaticity of Graphs. Singapore: World Scientific, 2005.Erdős, P. and Hajnal, A. "On Chromatic Numbers of Graphs and Set-Systems." Acta Math. Acad. Sci. Hungar. 17, 61-99, 1966.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 46, 1983.Read, R. C. "An Introduction to Chromatic Polynomials." J. Combin. Th. 4, 52-71, 1968.Saaty, T. L. and Kainen, P. C. "Chromatic Numbers and Chromatic Polynomials." Ch. 6 in The Four-Color Problem: Assaults and Conquest. New York: Dover, pp. 134-163 1986.Skiena, S. "Chromatic Polynomials." §5.5.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 210-212, 1990.Sloane, N. J. A. Sequences A104457 and A140986 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "Acyclic Orientations of Graphs." Disc. Math. 5, 171-178, 1973.Tutte, W. T. "On Chromatic Polynomials and the Golden Ratio." J. Combin. Th. 9, 289-296, 1970.Yadav, R.; Sehgal, A.; Sehgal, S.; and Malik, A. "The Chromatic Polynomial of Grid Graph P_3 square P_n." J. Appl. Math. Comput., 2024.

在 中被引用

色多項式

引用為

Weisstein, Eric W. "色多項式。" 來自 Web 資源。 https://mathworld.tw/ChromaticPolynomial.html

主題分類