# Question - Chromatic Polynomial for Given Graph

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?

• does the $9$ come from the fact that there are $\binom{5}{3}$ ways to choose $3$ vertices to color the same and since $1$ such way was accounted for in the first case that there are $9$ cases for the second case? – rover2 Dec 16 '18 at 23:41
• Do you insist on using the inclusion-exclusion principle? There are much easier ways to find the chromatic polynomial, but it makes sense to stick with this if you are primarily interested in "how do I make inclusion-exclusion work here?" not "how do I find the chromatic polynomial of this graph quickly?" – Misha Lavrov Dec 16 '18 at 23:43
• @MishaLavrov if i have done the quicker way correctly...is the chromatic polynomial $n(n-1)^3 (n-2)$...given that there are $n$ such available colors to use – rover2 Dec 16 '18 at 23:50
• $n$ choices for 1, $n-1$ choices for 2, $n-2$ choices for 3, then $n-1$ choices for each of 4 and 5. – Gordon Royle Dec 17 '18 at 0:15
• That is exactly the quick way to do it. – Misha Lavrov Dec 17 '18 at 0:30

• 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.