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

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

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

##### Finalizing the Calculation of \(P_{1.2^{\circ}}(k)\)

The vertex \(E\) cannot have a color from \(\{1,2,3\}\). We will consider two sub-cases. In the sub-case 1.2.1 we assume that the vertex \(E\) has the color \(4\). In the sub-case 1.2.2 we assume that the vertex \(E\) has one of the \((k-4)\) colors outside of the set \(\{1,2,3,4\}\). Let us denote by \(P_{1.2.1^{\circ}}\) the number of proper colorings in which the vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(G\), and \(H\) have the colors \(1\), \(2\), \(1\), \(1\), \(4\), \(4\), and \(3\), repsectively. Denote by \(P_{1.2.2^{\circ}}(k)\) the number of proper colorings in which the vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(G\), and \(H\) have the colors \(1\), \(2\), \(1\), \(2\), \(5\), \(4\), and \(3\), respectively.

The number \(P_{1.2^{\circ}}(k)\) can be expressed in terms of these newly introduced numbers as \[P_{1.2^{\circ}}(k)=P_{1.2.1^{\circ}}(k)+(k-4)P_{1.2.2^{\circ}}(k).\]

It remains to count the number of colorings for the vertex \(F\). The vertex \(F\) can have any color outside of \(\{1,2,4\}\). There are \(k-3\) such colors, hence \[P_{1.2.1^{\circ}}(k)=k-3.\]

The vertex \(F\) can have any color outside of the set \(\{1,2,4,5\}\). There are \(k-4\) available colors for \(F\) hence \[P_{1.2.2^{\circ}}(k)=k-4.\]

Using that \(P_{1.2^{\circ}}(k)=P_{1.2.1^{\circ}}(k)+(k-4)P_{1.2.2^{\circ}}(k)\), \(P_{1.2.1^{\circ}}(k)=k-3\), and \(P_{1.2.2^{\circ}}(k)=k-4\), we obtain \[P_{1.2^{\circ}}(k)=k-3+(k-4)^2.\]