Chromatic polynomial of a graph - might take a while

Question

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding or removing edges is the most efficient route to go for.

2 examples can be viewed here:

For the first image, I get that you can split it into 2, work on one of them, then square and divide by K2, but for the second one, I'm at a total loss.

Is there any magic trick to these that I just fail to see?

PS. I do get that you could pick one of the methods arbitrary, but, in both cases, we can see a cycle, meaning that removing edges is going to result in trees that contain quite alot of edges - the following simplification is going to contain numbers that are problematic in and of themselves (i.e., raised to the power of 9).

They don't really contain enough edges to make adding edges very efficient either. Also, I'm supposed to be able to do these, and the concluding simplification without any tool assistance ("by hand", shrug).

Answer 1

Note that we have four triangles and two four-cycles. So we take $P(C_{3})^{4} * P(C_{4})^{2}$. Each of the three-cycles share an edge, and two of the three cycles share an edge with the four cycles. So we divide out by $P(K_{2})^{6}$, the number of shared edges. So we have:

$$P(G) = \dfrac{ (k^{4} * (k-1)^{4} * (k-2)^{4}) * [(k * (k-1)^{3} - k(k-1)(k-2)]^{2}}{k^{6} * (k-1)^{6}}$$

Note that in general, calculating the chromatic polynomial is NP-Hard, as calculating the optimal coloring is NP-Hard. However, for many small graphs, you can reason out coloring restrictions as I did here.

Answer 2

For your second graph I would use the axiom of Total Adjacency: Given a graph $G$ which is the join of a single vertex $u$ with another graph ($u$ is adjacent to all other vertices) then $u$ must have a colour different from all other vertices; hence $P(G,t) = t \times P(G-u,t-1)$.

As previously discussed we then will have, by Complete Intersection: $$P(G,t) = \frac{P(C_4,t) \times P(K_1 + C_4,t) \times P(C_4,t)}{P(K_2,t) \times P(K_2,t)}$$

Taking the central term on its own we'll get $$P(K_1 + C_4,t) = t \times P(C_4 ,t-1) = t(t-1)(t-2)((t-1)^2 -3(t-1) +3) = t(t-1)(t-2)(t^2- 5t +7)$$ which is the term you were looking for.

If you aren't allowed to use Total Adjacency then it will be necessary to add an edge to move towards a complete graph as you've already done.

As a general strategy the idea is to choose to remove edges to create Complete Intersections and/or add/delete edges to make complete graphs, cycles or trees. With Total Adjacency you can also aim for a vertex of maximum valency...

The problem with ml0105's reasoning is that some triangles join to earlier triangles. The difference occurs if we have all different colours chosen for the 4 vertices of the first two triangles in which case there are k-3 choices for the fifth vertex. Note also that the degree of the polynomial is not the number of vertices which it must be.