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

The vertex \(F\) cannot have colors \(2\), \(4\), and \(5\). We will consider two sub-cases. In the sub-case 2.2.1.3.1 we count all the proper colorings of \(\Gamma\) in which the vertex \(F\) has color \(1\). In the sub-case 2.2.1.3.2 we count all the proper colorings of \(\Gamma\) in which the vertex \(F\) does not have a color from \(\{1,2,4,5\}\). In the sub-case 2.2.1.3.2 there are \((k-4)\) possible colors that can be assigned to \(F\).

Let \(P_{2.2.1.3.1^{\circ}}(k)\) be the number of proper colorings of \(\Gamma\) in which the vertices \(A\), \(B\), \(C\), \(D\), \(F\), \(G\), and \(H\) have the colors \(1\), \(4\), \(2\), \(3\), \(1\), \(5\), and \(2\), respectively. Let \(P_{2.2.1.3.2^{\circ}}(k)\) be the number of proper colorings of \(\Gamma\) in which the vertices \(A\), \(B\), \(C\), \(D\), \(F\), \(G\), and \(H\) have the colors \(1\), \(4\), \(2\), \(3\), \(3\), \(5\), and \(2\), respectively. The following identity holds

\[P_{2.2.1.3^{\circ}}(k)=P_{2.2.1.3.1^{\circ}}(k)+(k-4)P_{2.2.1.3.2^{\circ}}(k).\]
Case 2.2.1.3.1: Calculation of \(P_{2.2.1.3.1^{\circ}}(k)\)

It remains to count the number of ways in which the vertex \(E\) can be colored. The vertex \(E\) must not have any of the colors \(1\), \(2\), and \(4\). That leaves \(k-3\) available colors for the vertex \(E\). Therefore \[P_{2.2.1.3.1^{\circ}}(k)=k-3.\]

Case 2.2.1.3.2: Calculation of \(P_{2.2.1.3.2^{\circ}}(k)\)

The vertex \(E\) must not have any of the colors \(1\), \(2\), \(3\), and \(4\). The number of available colors for \(E\) is \(k-4\). Therefore \[P_{2.2.1.3.2^{\circ}}(k)=k-4.\]

Thus we have \begin{eqnarray*}P_{2.2.1.3^{\circ}}(k)&=&P_{2.2.1.3.1^{\circ}}(k)+(k-4)P_{2.2.1.3.2^{\circ}}(k)\newline &=&k-3+(k-4)^2. \end{eqnarray*}