在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。 色多项式 P ( G , t ) {\displaystyle P(G,t)} 的值是在图 G {\displaystyle G} 中顶点的不同的 t {\displaystyle t} -着色数目，是关于 t {\displaystyle...

(G)=\min\{k\,\colon \,P(G,k)>0\}.} 下表给出了部分图的色多项式： 五色定理 四色定理 Vizing定理 布鲁克定理 Konig定理（关于二分图） Hadwiger猜想 拉姆齐定理 色数 NP-complete問題列表 幾乎完備（Almost complete（英语：Almost...

的结构直接相关，尤其是与不可约特征标相关。 最后，代数图论的第三个分支研究图不变量的代数性质，尤其是色多项式、Tutte多项式与扭结不变量。例如，图的色多项式计算了顶点着色的个数。佩特森图的色多项式为 t ( t − 1 ) ( t − 2 ) ( t 7 − 12 t 6 + 67 t 5 − 230...

个可有效计算这种常量的方法(图规范化问题)等价于给出一个简单解决富有挑战性的图同构问题的方法。然而，即使多项式的常量值如色多项式，通常也不完备的。例如，爪形图和4个顶点的道路图都具有相同的色多项式。 连通图 二分图 平面图 无三角形图 完美图 欧拉图 汉密尔顿图 顶点数 边数 元件数 电路等级（图的顶点、边和元件的线性组合）...

如果这样的k着色方式存在，那么我们为了给整个图着色的最小着色数（k值）可记为 χ ( G ) {\displaystyle \chi (G)} 。 我们可以通过构建k的多项式函数来计算合理的k着色方式的数量，其被称为图G的着色多项式（可用无向图的着色多项式来类比），其定义式为 χ G ( k ) {\displaystyle...

graph），其色数为3：环上的节点可以用两种颜色染色，而中间的完全点使用第三种颜色。当n为偶数时，Wn的色数为4，且当n ≥ 6时不是完美图。W7是轮图中在欧几里得平面上的唯一一个单位距离图（英语：unit distance graph）。 轮图Wn的色多项式为 P W n ( x )...

4的情况，阿佩尔和哈肯在1989年的单行本的附录中给出一个完整的多项式时间的算法及其证明。 四色问题探讨的是平面上地图的染色问题。更一般的情况：曲面上地图的染色问题是由希伍德开始研究的。他在1890年的论文中不仅指出肯普的错误，而且运用肯普的方法证明了五色定理。在此之后，希伍德又将注意力转移到更一般的曲面染色...

交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP完備問題得到多項式時間內的解法，則該解法就可應用在所有NP問題上，亦可證明NP問題等於P問題，然而目前為止並未發現任何能在多項式時間內解決NP完備問題的方法。...

代数几何（英語：algebraic geometry）是数学的一个分支，经典代数几何研究多项式方程的零点。现代代数几何将抽象代数，尤其是交换代数，同几何学的语言和问题结合起来。 代数几何的基本研究对象为代数簇。代数簇是由空间坐标的若干代数方程的零点集。常见的例子有平面代数曲线，比如直线、圆、椭圆、...

如果只有两项作业或两个工作站，那么开放车间调度问题可以在多项式时间内求解。如果说所有不等于0的解决时间都相等，那么这种问题也可以在多项式时间内完成。因为在这种情况下，这个问题可以等效于给一个以作业和工作站为顶点的二分图的边上色，每条边代表不为0的作业-工作站对，着色中边的颜色对应于工作-工...

红磷（英語：Red Phosphorus），磷的一种同素异形体 反相色谱法（英語：Reverse phase），一种色谱技术 RP-3，一种火箭弹 RP (复杂度)（英語：RP (complexity)），随机多项式时间，计算复杂度理论中的一类 数学 实射影直线（英語：Real projective...