1
$\begingroup$

Let $G$ be the graph in picture:

enter image description here

calculate the chromatic polynomial of it.

My attempt:

I assume that $G(K_n,x)$ is the number of distinct colors of the complete graph with $n\geq1$ vertices with at most $x$ colors. So, in case of a classic square it'll be:

$G(K_4,x) = x(x-1)(x-2)(x-3) = x^4-6x^3+11x^2-6x$

but here we have one more edge between two nodes. What should I do?

$\endgroup$
  • $\begingroup$ You mention a square, which is different from $K_4$. You have one fewer edge than $K_4$, not one more. $\endgroup$ – Théophile Aug 19 '14 at 17:13
3
$\begingroup$

Consider coloring the vertices one at a time, with $x$ colors. Beginning with the upper left vertex, you have $x$ choices of color for that vertex. Once that color is chosen, there are $x-1$ choices of color for the lower left vertex (it cannot have the same color as the upper left vertex). Once those colors are chosen, there are $x-2$ choices of color for the upper right vertex (it cannot have the same color as the upper left or lower left). Finally, there are $x-2$ choices for the lower right vertex (it cannot have the same color as the lower left or upper right). So we have:

$$\chi(G,x) = x(x-1)(x-2)^2 = x^4 - 5x^3 + 8x^2 - 4x$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.