# Chromatic polynomial of a $8$-vertex graph

I'm supposed to determine chromatic polynomial of a $8$-vertex graph, which is the result of sticking

There are two complete $5$-vertex graphs, each with one edge removed, in the first graph we remove the edge $uv$ and in the second graph we remove $u'v'$. Then we stick the graphs together by putting $u=u'$ and $v=v'$ . I hope the description is quite clear, because I don't know how to insert the image of this graph.

It seems pointless to try using the recurrence formula for chromatic polynomial of a graph (by trying to get complete graphs by contracting together two unconnected vertices and drawing an additional edge linking them).

Could you help me with that?

-
If we take two copies of $K_5$ and merge two vertices in one copy with two vertices in the other, the resulting graph has only eight vertices. –  Chris Godsil Jan 29 '13 at 19:29
Oh, right, it is an 8-vertice graph. –  Hagrid Jan 29 '13 at 20:59

It's easy to see this from first principles: remember that $P(x)$ is the number of colourings of the graph using $x$ colours.

If you fix the colours of the two vertices in the middle (which used to be $u$ and $v$), then the remaining graph splits into two separate complete graphs which are very simple to count colourings in.

(At this point you should ask yourself: if there are $3$ ways to colour each copy, how many different ways are there to colour both together? Hint: it's not $6$.)

The exact number of colourings of each complete graph (as a function of $x$) depends on whether you colour $u$ and $v$ the same colour or distinct colours, so consider these two cases separately, and remember to account for how many ways there are to choose the two initial colours.

-
Well, if we consider a graph with 5 vertices where $u$ and $v$ are not connected then for such a graph if $u$ and $v$ have different colours we get x(x-1)(x-2)(x-3)(x-4) possible colourings and if $u$ and $v$ have the same colours we get x(x-1)(x-2)(x-3) possible colourings. Now, the answer in my textbook is $\frac{(x(x-1)(x-2)(x-3)(x-4))^2}{x(x-1)} + \frac{(x(x-1)(x-2)(x-3))^2}{x}$. Could you tell me what to do next? Or did I just understand you incorrectly? –  Hagrid Jan 29 '13 at 21:23
@Hagrid You're on the right track but you need to take into account that your graph contains two such graphs of 5 vertices. There are $x(x-1)$ ways to choose $u$ and $v$ with different colours, and $x$ ways to choose them with the same colour. How many choices for the remaining 6 vertices? It helps if you have given some thought about where formulas like $x(x-1)(x-2)(x-3)$ come from. –  Erick Wong Jan 29 '13 at 21:41
From the picture that @Robert Israel presented below we can see that if $u, \ v$ have the same colour, then we choose colour of the base and then of the vertices of three triangles in x(x-1)(x-2)(x-3) ways and if their colours are different we do it in x(x-1)(x-2)(x-3)(x-4) ways. Is that correct? –  Hagrid Jan 29 '13 at 22:09
@Hagrid Let's make this more concrete by picking, say $x=6$. There are $6\cdot 5 = 30$ ways to colour $u$ and $v$ differently. Now there are $4$ colours remaining, since we cannot reuse $u$ and $v$'s colours: how many ways can you colour all six remaining vertices? (Certainly there is more freedom in colouring two triangles than just one of them.) –  Erick Wong Jan 29 '13 at 22:41
Having coloured the two middle vertices (1 and 2), we can the colour the "3" in 4 ways, "4" in 3 ways and "5" in 2 ways. Since We can repeat it for "3'", "4'", "5'" because they are not directly linked to "3", "4", "5". –  Hagrid Jan 29 '13 at 23:10

I assume this is your graph. Shown is a 4-colouring. It's easy to see there are $4$-cliques, so the chromatic number is $4$.

EDIT: I suggest you look at two separate cases, where $1$ and $2$ have the same colour and where they have different colours. Note that given the colours of vertices $1$ and $2$, vertices $3$, $4$ and $5$ can have any three different colours that are not those of $1$ and $2$, and similarly for $3'$, $4'$ and $5'$.

-
But the question asks for the chromatic polynomial, not the chromatic number. –  Chris Godsil Jan 29 '13 at 21:33
Yes, but see the last paragraph. –  Robert Israel Jan 29 '13 at 21:47

So, here's the graph:

and another method for finding the chromatic polynomial.

We can use the addition/identification law on the vertices $x$ and $y$ to compute the chromatic polynomial. The law states that if $x$ and $y$ are not adjacent, then the $$P(G,\lambda)=P(G+xy,\lambda)+P(G/xy,\lambda).$$

In this case, the chromatic polynomial of the above graph is the sum of the chromatic polynomials of the graphs:

and

These graphs are clique separable copies of complete graphs. Thus, they have the chromatic polynomials $$\frac{P(K_5;\lambda)^2}{P(K_2;\lambda)}$$ and $$\frac{P(K_4;\lambda)^2}{P(K_1;\lambda)},$$ respectively.

The chromatic polynomial of the complete graph $K_n$ is $$P(K_n;\lambda)=\lambda(\lambda-1)\cdots(\lambda-n+1).$$

Hence the chromatic polynomial of the original graph is: $$\frac{\big(\lambda(\lambda-1)(\lambda-2)(\lambda-3)(\lambda-4)\big)^2}{\lambda(\lambda-1)}+\frac{\big(\lambda(\lambda-1)(\lambda-2)(\lambda-3)\big)^2}{\lambda}$$ which simplifies to $$\lambda(\lambda-1)(\lambda-2)^2(\lambda-3)^2(\lambda-7\lambda+15).$$

-