I am trying to find the chromatic polynomial for the graph below:
I am using the inclusion-exclusion principle. Here are my bad cases:
$A_1 = \{1 \text{ and } 2 \text{ colored the same }\}$
$A_2 = \{1 \text{ and } 3 \text{ colored the same }\}$
$A_3 = \{2 \text{ and } 3 \text{ colored the same }\}$
$A_4 = \{2 \text{ and } 5 \text{ colored the same }\}$
$A_5 = \{3 \text{ and } 4 \text{ colored the same }\}$
For $|A_i \cap A_j \cap A_k|$, there are two cases that can occur:
Either $1,2,3$ are colored the same: $1\cdot n^3$ ways for this coloring. Or for example, $1,2,3,4$ are colored the same: $n^2$ ways for this coloring. It was determined during my lecture class that there are $9$ such cases for this type of coloring. However I am having trouble understanding how there are $9$ such cases. Can someone explain?
Best Answer
Here is the inclusion-exclusion method in detail:
Altogether, we get $$ n^5 - 5n^4 + 10n^3 - (n^3 + 9n^2) + (2n^2+3n) - n = n^5 - 5n^4 + 9n^3 - 7n^2 + 2n $$ colorings.
The general pattern we see in these calculations is that if we're taking an intersection $A_i \cap A_j \cap \dots$, then the number of cases in that intersection is $n^k$, where $k$ is the number of connected components in the subgraph formed by the edges that $A_i, A_j, \dots$ check.