Back to: Chromatic Polynomial
##### Case 2.2: Calculation of $$P_{2.2^{\circ}}(k)$$ We will now consider two sub-cases: Sub-case $$2.2.1^{\circ}$$ is when the vertex $$H$$ is of one of the colors $$\{2,4\}$$; and sub-case $$2.2.2^{\circ}$$ is when the vertex $$H$$ does not have one of the colors from $$\{2,4\}$$.

The number of proper colorings in which $$H$$ has color $$2$$ is equal to the number of proper colorings in which $$H$$ is of color $$4$$. Therefore we will cacluate only the number of proper colorings in which $$H$$ has color $$2$$. We will denote by $$P_{2.2.1^{\circ}}(k)$$ the number of proper colorings in which $$H$$ has color $$2$$, and as specified earlier $$A$$, $$B$$, $$C$$, and $$D$$ have colors $$1$$, $$4$$, $$2$$, and $$3$$ respectively.

Notice that $$H$$ cannot have color $$1$$ nor color $$3$$. Therefore, if $$H$$ has a color outside of the set $$\{2,4\}$$, then $$H$$ must not have any of the colors from $$\{1,2,3,4\}$$. The number of colorings in the case $$2.2.2^{\circ}$$ is $$(k-4)\cdot P_{2.2.2^{\circ}}(k)$$ where $$P_{2.2.2^{\circ}}(k)$$ is the number of proper colorings of $$\Gamma$$ in which $$A$$, $$B$$, $$C$$, $$D$$, and $$H$$ have colors $$1$$, $$4$$, $$2$$, $$3$$, and $$5$$ respectively.

The number $$P_{2.2^{\circ}}(k)$$ satisfies $P_{2.2^{\circ}}(k)=2\cdot P_{2.2.1^{\circ}}(k)+(k-4)\cdot P_{2.2.2^{\circ}}(k).$

Therefore the polynomial $$P_{2.2^{\circ}}(k)$$ satisfies \begin{eqnarray*}P_{2.2^{\circ}}(k)&=&2\cdot P_{2.2.1^{\circ}}(k)+(k-4)\cdot P_{2.2.2^{\circ}}(k)\newline &=&2\left(k^3-9k^2+28k-31\right)+(k-4)\left(k^3-10k^2+36k-47\right)\newline &=&2k^3-18k^2+56k-62+(k-3)\left(k^3-10k^2+36k-47\right)-\left(k^3-10k^2+36k-47\right)\newline &=&k^3-8k^2+20k-15+(k-3)\left(k^3-10k^2+36k-47\right)\newline &=&k^3-3k^2-5k^2+15k+5k-15+(k-3)\left(k^3-10k^2+36k-47\right)\newline &=&(k-3)\left(k^2-5k+5\right)+(k-3)\left(k^3-10k^2+36k-47\right)\newline \ &=&(k-3)\left(k^3-9k^2+31k-42\right). \end{eqnarray*}