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?

  • $\begingroup$ 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? $\endgroup$ – rover2 Dec 16 '18 at 23:41
  • $\begingroup$ 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?" $\endgroup$ – Misha Lavrov Dec 16 '18 at 23:43
  • 2
    $\begingroup$ @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 $\endgroup$ – rover2 Dec 16 '18 at 23:50
  • 1
    $\begingroup$ $n$ choices for 1, $n-1$ choices for 2, $n-2$ choices for 3, then $n-1$ choices for each of 4 and 5. $\endgroup$ – Gordon Royle Dec 17 '18 at 0:15
  • 1
    $\begingroup$ That is exactly the quick way to do it. $\endgroup$ – Misha Lavrov Dec 17 '18 at 0:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.