4
$\begingroup$

for a homework graph theory, I'm asked to determine the chromatic polynomial of the following graph

this is my thread in another post:

https://stackoverflow.com/questions/5724167/problem-to-determine-the-chromatic-polynomial-of-a-graph

For the Descomposition Theorem of Chromatic Polynomials. if G=(V,E), is a connected graph and e belong E

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

When calculating chromatic Polynomials, i shall place brackets about a graph to indicate its chromatic polynomial. removes an edge any of the original graph to calculate the chromatic polynomial by the method of decomposition.

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

But the response from the answer key and the teacher is:

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

I have operated on the polynomial but I can not reach the solution that I ask .. what am I doing wrong?

2 Answers 2

3

Your graph is a 5-cycle. I wouldn't use that theorem, I'd just do it directly.

1st vertex: $\lambda$ options.

2nd vertex: $\lambda-1$ options.

3rd vertex: two cases. If it's the same color as 1st vertex, then $\lambda-1$ options for 4th vertex, $\lambda-2$ options for 5th vertex. So this case contributes $\lambda(\lambda-1)^2(\lambda-2)$. Second case, if it differs from the 1st vertex ($\lambda-2$ options), then two subcases: if 4th vertex is same color as 1st, then $\lambda-1$ options for 5th, making $\lambda(\lambda-1)(\lambda-2)(\lambda-1)$. If 4th differs from 1st ($\lambda-2$ options), then $\lambda-2$ options for 5th, making $\lambda(\lambda-1)(\lambda-2)^3$.

Now add 'em all up.

  • 1
    @Soura, I'm not sure which two answers you are asking about. The answer OP got has degree four, so it can't be right; the degree must equal the number of vertices.2017-04-07
1

I think what you need in your answer is $\lambda (\lambda- 1)^4$ for the polynomial of Ge. The 5-cycle with one edge removed is a path of five vertices. $\lambda$ choices for the first, and $(\lambda - 1)$ choices for the other 4.