主题
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 多项式, 顶点着色

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

色多项式

引用为

Weisstein, Eric W. "色多项式。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ChromaticPolynomial.html

主题分类