Back to: Chromatic Polynomial Case \(2.2^{\circ}\)
Case 2.2.1: Calculation of \(P_{2.2.1^{\circ}}(k)\)

Observe that the vertex \(G\) cannot have a color \(2\) or \(3\). We will consider 3 sub-cases. Sub-case 2.2.1.1 is in which the vertex \(G\) has color \(1\). Sub-case 2.2.1.2 is the sub-case in which \(G\) has color \(4\), and sub-case 2.2.1.3 is the sub-case in which \(G\) has a color outside of the set \(\{1,2,3,4\}\).

Let us introduce the following polynomials that correspond to sub-cases 2.2.1.1, 2.2.1.2, and 2.2.1.3.

The polynomial \(P_{2.2.1^{\circ}}(k)\) can be expressed in terms of these newly introduced polynomials as \[P_{2.2.1^{\circ}}(k)=P_{2.2.1.1^{\circ}}(k)+P_{2.2.1.2^{\circ}}(k)+(k-4)P_{2.2.1.3^{\circ}}(k).\] The last polynomial is multiplied by \((k-4)\) because if the vertex \(G\) does not have any of the colors from \(\{1,2,3,4\}\), then the number of available colors for \(G\) is \(k-4\).

Therefore the polynomial \(P_{2.2.1^{\circ}}(k)\) satisfies \begin{eqnarray*} P_{2.2.1^{\circ}}(k)&=&P_{2.2.1.1^{\circ}}(k)+P_{2.2.1.2^{\circ}}(k)+(k-4)P_{2.2.1.3^{\circ}}(k)\newline &=&(k-3)(k-4)+(k-3)^2+(k-4)\left( k-3+(k-4)^2\right)\newline &=&k^3-9k^2+28k-31. \end{eqnarray*}