Chromatic Polynomial

释义 Definition

染色多项式：图论中的一个多项式 (P_G(k))，表示给定图 (G) 用 (k) 种颜色对顶点进行合法着色（相邻顶点颜色不同）的方案数。它是关于 (k) 的多项式，用来研究图的可着色性与组合结构。（在不同语境下也可能讨论其系数、零点等性质。）

发音 Pronunciation (IPA)

/krəˈmætɪk ˌpɑːlɪˈnoʊmiəl/

例句 Examples

We computed the chromatic polynomial of a triangle graph.
我们计算了三角形图的染色多项式。

The chromatic polynomial links graph coloring to algebra, and its evaluation at specific integers counts proper colorings.
染色多项式把图着色问题与代数联系起来，并且在特定整数处的取值会给出合法着色的数量。

词源 Etymology

chromatic 源自希腊语 khrōma（颜色），在数学里常指“与颜色/着色有关”。polynomial 来自 *poly-*（多）与 nomial（项/名称），指“多项式”。“chromatic polynomial”这一术语与图着色研究紧密相关，早期系统研究可追溯到 George D. Birkhoff 在 20 世纪初关于图着色与多项式计数的工作。

相关词 Related Words

• Chromatic
• Polynomial
• Graph
• Vertex
• Edge
• Graph Coloring
• Proper Coloring
• Chromatic Number
• Deletion–Contraction
• Tutte Polynomial

文学与著作中的用例 Literary Works

• George D. Birkhoff（1912）, A Determinant Formula for the Number of Ways of Coloring a Map（提出并推动了用多项式计数图着色的经典思路，染色多项式相关内容常在此脉络中被引用）
• Douglas B. West, Introduction to Graph Theory（图论教材中通常专章介绍染色多项式与递推法）
• J. A. Bondy & U. S. R. Murty, Graph Theory（包含图着色与染色多项式的标准论述）
• Reinhard Diestel, Graph Theory（在图着色部分常讨论染色多项式的性质与应用）