Coloring simple graph

Question

Given a graph with $5$ vertices and $6$ edges. Find the chromatic number and polynomial.

The chromatic number is trivial, it would of course be $3$. But I am completely clueless on how to find the chromatic polynomial. I know there's no effective algorithm, but is there any shortcut to these graphs, such as there is with complete graphs?

Answer 1

You can use the Fundamental Reduction Theorem many times. It states that

$$P(G,t)=P(G-uv,t)-P(G/uv,t)$$ where $u$ and $v$ are two adjacent vertices, $G-uv$ is the graph obtained by removing the edge $uv$ and $G/uv$ is the graph obtained by contracting the vertices $u$ and $v$.

After two times you should obtain $$ P(P_5,t)-P(P_4,t)-P(P_4,t)+P(P_3,t), $$ where $P_j$ is the path graph with $j$ vertices.

You know that the chromatic polynomial for a path graph (in general for a tree) with $n$ vertices has chromatic polynomial $$P(P_j,t)=t(t-1)^{n-1}.$$ Hence $$P(G,t)=t(t-1)^2\left[(t-1)^2-2(t-1)+1\right]=t(t-1)^2(t-2)^2. $$

Answer 2

Have you tried the deletion-contraction algorithm given in http://en.wikipedia.org/wiki/Chromatic_polynomial

Answer 3

Given a palette of $x$ colors, there are $x$ ways to color the middle vertex, then $x-1$ choices for the upper left vertex, $x-2$ for the lower left, $x-1$ for the upper right, $x-2$ for the lower right, so $x(x-1)^2(x-2)^2$.