Question – Chromatic Polynomial for Given Graph

coloringgraph theory

I am trying to find the chromatic polynomial for the graph below:

enter image description here

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:

  • First, we count $|A_1| + |A_2| + |A_3| + |A_4| + |A_5| = 5n^4$. Here, nothing interesting happens: if two vertices are colored the same, we just choose both colors at once.
  • Second, we count $|A_1\cap A_2| + |A_1\cap A_3| + \dots + |A_4 \cap A_5| = 10n^3$. Here, there are two cases that seem different, but they have the same count. $A_1 \cap A_2$ is the first kind: if $1$ and $2$ are the same, and $1$ and $3$ are the same, then we color $\{1,2,3\}$, then $4$, then $5$. $A_1 \cap A_5$ is the second kind: if $1$ and $2$ are the same, and $3$ and $5$ are the same, then we color $\{1,2\}$, then $\{3,5\}$, then $4$.
  • Next, we count the threefold intersections. Here $A_1\cap A_2 \cap A_3$ forces $1,2,3$ to be the same, so we color $\{1,2,3\}$ then $4$ then $5$ in $n^3$ ways. However, this is the only triple intersection of its kind. If we have $A_1 \cap A_2\cap A_4$, then $1$ and $2$ are the same, $1$ and $3$ are the same, and $2$ and $5$ are the same, so we color $\{1,2,3,5\}$ then $4$ in $n^2$ ways. The intersection $A_1\cap A_2 \cap A_3$ is the only one that gives us $3$ things to choose instead of $2$. Altogether, we have $$|A_1\cap A_2\cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_2 \cap A_5| + |A_1 \cap A_3\cap A_4| + |A_1 \cap A_3 \cap A_5| + |A_1 \cap A_4 \cap A_5| + |A_2 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_5| + |A_2 \cap A_4 \cap A_5| + |A_3 \cap A_4 \cap A_5| = n^3 + 9n^2.$$
  • The four-fold intersections also come in two types. Some force all 5 vertices to have the same color and some don't. So for example there are only $n$ cases that fall under $A_1 \cap A_2 \cap A_4 \cap A_5$ since this forces all vertices to be the same color; but there are $n^2$ cases that fall under $A_1 \cap A_2 \cap A_3 \cap A_4$ since vertex $4$ can be different from $\{1,2,3,5\}$. The only other intersection with $n^2$ cases is $A_1 \cap A_2 \cap A_3 \cap A_5$, and we know this because vertices $4$ and $5$ are the only ones with only one edge. Altogether, we have $$|A_1\cap A_2 \cap A_3 \cap A_4| + |A_1\cap A_2 \cap A_3 \cap A_5| + |A_1 \cap A_2 \cap A_4 \cap A_5| + |A_1 \cap A_3 \cap A_4 \cap A_5| + |A_2 \cap A_3 \cap A_4 \cap A_5| = 2n^2 + 3n.$$
  • There is only one five-fold intersection, and then there are $n$ colorings it counts because all vertices have to be the same.

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.

Related Question