Determine the chromatic polynomial of the given graph

Question

Problem: Determine the chromatic polynomial of the graph $G$ below, using known chromatic reduction formulas. That is, solve this without using any computer programs.

Formulas:

($1$): For a graph $G$, if $e$ = $uv$ $\in E(G)$, then $p(G, r)$ = $p(G - e, r)$ $-$ $p(G/e, r)$, where the contraction $G/e$ is the graph obtained from $G - e$ by coalescing vertices $u$ and $v$ and deleting any redundant edges.

($2$): If the graph $G$ is an overlap of graphs $G_{1}$ and $G_{2}$ in $K_{n}$, then $p(G, r) = (p(G_{1}, r)\cdot\ p(G_{2}, r)) / p(K_{n}, r)$

My thinking:

• I can begin by using the known formula for the wheel graph $W_{n}$, $p(W_{n}, r) = r[(r-2)^{n-1} - (-1)^{n}(r-2)]$. More specifically, I choose to start with the wheel $W_{7}$ that one can easily see.
• I use formula $(2)$ to find the chromatic polynomial of the graph consisting of $W_{7}$ and the most upper left vertex and its two edges that connect to $W_{7}$ (i.e. the upper left triangle). We'll call it $G_{1}$. So, $G_{1}$ is an overlap of $W_{7}$ and $K_{3}$ in $K_{2}$.
• Then, I focus on the vertex and two edges on the exact opposite side (the right side of the entire graph). This graph, we'll call it $G_{2}$, is an overlap of $H$ and $K_{3}$ in $K_{2}$. Using formula $(2)$, we can find the chromatic polynomial after some simple algebra.
• Now, I decide to consider the top-most vertex and the two edges that fall to the left (geometrically, I'm referring to the top-most left right triangle). Call the graph $G_{3}$ that is an overlap of $G_{2}$ and $K_{3}$ in $K_{2}$. I can use formula $(2)$ to find the chromatic polynomial of $G_{3}$.
• Lastly, I am still left with one "triangle" that has yet to be accounted for. I'm referring to the final edge of the entire graph $G$ (the upper right slanted edge of the right triangle on the upper right side).

Question: How can I now include this one last edge to determine the entire graph's chromatic polynomial?

NOTES: Sorry for so many words. If it's hard to follow my line of thinking, then don't worry about it. All I want to know is how to find the chromatic polynomial of this graph.

Answer 1

You can continue by using (1) twice more (recursively), once with the top right edge and then the top left edge.

Alternatively, you can start over and use (1) in reverse by adding an edge in the middle to get a 4-clique sum of wheels $W_7$ and $W_6$.

Answer 2

Let's break the problem into three relatively easier ones.

$G_1$

$$p(G_1,r)=r[(r-2)^5-(r-2)]-r(r-1)(r-2)^2(r-3)$$ $$=r(r-1)(r-2)(r-3)[(r-2)(r-3)+1]$$

$G_2$

$$p(G_2,r)=r[(r-2)^6+(r-2)](r-2)-r[(r-2)^4+(r-2)](r-2)^2$$ $$=r(r-1)(r-2)^2(r-3)^2[(r-2)^2+1]$$

$G_3$

$$p(G_3,r)=r[(r-2)^4+(r-2)](r-2)^3(r-3)$$ $$=[(r-2)(r-3)+1]r(r-1)(r-2)^4(r-3)$$

We can glue $G_1$ and $G_2$ together with formula $(2)$ and then use the result with $G_3$ and formula $(1)$ to get

$p(G,r)=\frac{\Big(r(r-1)(r-2)(r-3)[(r-2)(r-3)+1]\Big)\Big(r(r-1)(r-2)^2(r-3)^2[(r-2)^2+1]\Big)}{r(r-1)(r-2)(r-3)}+[(r-2)(r-3)+1]r(r-1)(r-2)^4(r-3)$

$=[(r-2)(r-3)+1]r(r-1)(r-2)^2(r-3)[(r-2)^3+(r-3)]$

Let me know if there are parts you want me to elaborate on.