图的色多项式的确定问题

Question

对于家庭作业图论，我被要求确定以下图的色多项式

​

​

关于色多项式的解组合定理，.若G=(V，E)是连通图，E属于E

P (G, λ) = P (Ge, λ) -P(Ge', λ)

其中Ge表示通过从G (Ge= G-e)中删除de边e得到的de子图，Ge‘是通过识别顶点{a，b} =e得到的子图。

在计算色多项式时，我会在图上加上括号来表示它的色多项式。用分解的方法移除原始图的任何边来计算色多项式。

​

​

 P (G, λ) = P (Ge, λ)-P (Ge', λ) = λ (λ-1)^4 - [λ(λ-1)*(λ^2 - 3λ + 3)]

但答案键和老师的反应是：

P (G, λ) = λ (λ-1)(λ-2)(λ^2-2λ-2)

我对多项式进行了运算，但我无法达到我所要求的解。我做错什么了？

Answer 1

math.stackexchange.com告诉我解决问题的方法。以下是解决办法：

https://math.stackexchange.com/questions/33946/problem-to-determine-the-chromatic-polynomial-of-a-graph

Answer 2

你的答案是正确的，老师的答案也是正确的--它们是平等的。顺便说一句，很好的图片和解释。

奇数圈不能有2-染色，因此5-圈不能有2-染色，所以它的色多项式f(x)必须有x*x-1*x-2。

作为除数。如果将f(x)的表达式组合起来并将

x * [x - 1]

然后你会发现剩下的东西可以被x- 2除以，而商是你老师写的。-Jonathan国王

Answer 3

在我下面的书(图论与应用-迪奥普伦提斯霍尔)，这是不同的做法。它们不排除边缘，而是连接两个不相邻的顶点。

用我得到的这个技巧

P (G, λ) = 2λ(λ-1)^2(λ-2) + 2λ(λ-1)(λ-2)(λ-3) + λ(λ-1)(λ-2)(λ-3)(λ-4)，也不等于您的结果之一。

​

​