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

Observe that none of the vertices \(E\) and \(H\) can have color \(1\) or color \(3\). We will consider two sub-cases: Sub-case 2.1.1 is when one of the vertices \(E\) and \(H\) has the color \(2\). The sub-case 2.1.1 is when none of \(E\) and \(H\) has a color from \(\{1,2,3\}\).

In the case 2.1.1 the number of colorings in which \(E\) has the color \(2\) is equal to the number of colorings in which \(H\) has the color \(2\). If the vertex \(E\) has the color \(2\) then there are \(k-3\) choices for the color of \(H\). Let us denote by \(P_{2.1.1^{\circ}}(k)\) the number of proper colorings of \(\Gamma\) in which \(A\), \(B\), \(C\), \(D\), \(E\), and \(H\) have the colors \(1\), \(3\), \(2\), \(3\), \(2\), and \(4\). The total number of colorings in the case 2.1.1 is \(2\cdot (k-3)\cdot P_{2.1.1^{\circ}}(k)\).

In the case 2.1.2 the vertices \(E\) and \(H\) cannot have any of the colors from \(\{1,2,3\}\). In addition, the vertices \(E\) and \(H\) must be of mutually different colors. There are \(k-3\) choices for the color of \(E\) and for each of those choices there are \(k-4\) available colors for \(H\). Let us denote by \(P_{2.1.2^{\circ}}(k)\) the number of proper colorings of \(\Gamma\) in which \(A\), \(B\), \(C\), \(D\), \(E\), and \(H\) have the colors \(1\), \(3\), \(2\), \(3\), \(4\), and \(5\), respectively. The total number of colorings in the case 2.1.2 is \((k-3)(k-4)P_{2.1.2^{\circ}}(k)\).

Therefore the polynomial \(P_{2.1^{\circ}}(k)\) satisfies \[P_{2.1^{\circ}}=2(k-3)P_{2.1.1^{\circ}}(k)+(k-3)(k-4)P_{2.1.2^{\circ}}(k).\]

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

The vertex \(G\) cannot have any of the colors \(2\), \(3\), and \(4\). There are \(k-3\) colors available for \(G\). For any of those \(k-3\) choices there are exactly \(k-3\) colors available for \(F\) (the color \(4\) is back as an option for \(F\), but the color that \(G\) took is out). Therefore \[P_{2.1.1^{\circ}}(k)=(k-3)^2.\]

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

The case 2.1.2 further brakes into two sub-cases. Let us observe the vertex \(F\). The vertex \(F\) cannot have any of the colors from the set \(\{2,3,4\}\). We will consider the sub-case 2.1.2.1 in which the vertex \(F\) has the color 5, and the sub-case 2.1.2.2 in which the vertex \(F\) has a color outside of the set \(\{2,3,4,5\}\). In the sub-case 2.1.2.2 there are \(k-4\) possibilities for \(F\).

Denote by \(P_{2.1.2.1^{\circ}}(k)\) the number of proper colorings of \(\Gamma\) such that the vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), and \(H\) have the colors \(1\), \(3\), \(2\), \(3\), \(4\), \(5\), and \(5\), respectively. Denote by \(P_{2.1.2.2^{\circ}}(k)\) the number of proper colorings of \(\Gamma\) such that the vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), and \(H\) have the colors \(1\), \(3\), \(2\), \(3\), \(4\), \(1\), and \(5\), respectively.

The number \(P_{2.1.2^{\circ}}(k)\) satisfies \[P_{2.1.2^{\circ}}(k)=P_{2.1.2.1^{\circ}}(k)+(k-4)P_{2.1.2.2^{\circ}}(k).\]

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

It remains to count the number of ways to color the vertex \(G\) that would complete the proper coloring of \(\Gamma\). The vertex \(G\) cannot have any of the colors from the set \(\{2,3,5\}\). Therefore there are \(k-3\) available colors for \(G\). Hence \[P_{2.1.2.1^{\circ}}(k)=k-3.\]

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

The vertex \(G\) cannot have any of the colors from the set \(\{1,2,3,5\}\). Therefore there are \(k-4\) available colors for \(G\) and \[P_{2.1.2.2^{\circ}}(k)=k-4.\]

Final Calculation of \(P_{2.1^{\circ}}(k)\)

We now have all the ingredients to complete the calculation of \(P_{2.1^{\circ}}(k)\). \begin{eqnarray*}P_{2.1^{\circ}}(k)&=&2(k-3)P_{2.1.1^{\circ}}(k)+(k-3)(k-4)P_{2.1.2^{\circ}}(k)\newline &=&2(k-3)\cdot (k-3)^2+(k-3)(k-4)\left(P_{2.1.2.1^{\circ}}(k)+(k-4)P_{2.1.2.2^{\circ}}(k)\right)\newline &=&2(k-3)^3+(k-3)(k-4)\left(k-3+(k-4)\cdot(k-4)\right)\newline &=&(k-3)\left[2(k-3)^2+(k-3)(k-4)+(k-4)^3\right]\newline &=&(k-3)\left(k^3-9k^2+29k-34\right). \end{eqnarray*}