Number of independent vertex sets in a graph. Consider the article http://math.mit.edu/~csikvari/chromatic_polynomial.pdf .
The author considers a graph $G$ with $n$ vertices and he wants to show that the chromatic polynomial $ch(G,q)$ of $G$ with $q$ colors is a polynomial. In the proof of proposition 1.2, the author uses $a_k$ to denote the number
of decompositions of the vertex set into $k$ independent sets. 
I understand that an independent vertex set is one that contains vertices that no two of them are linked with an edge.
My problem is to understand the number $a_k$, I need it for a combinatorial problem. Do we have a formula for $a_k$. I think there is no simple closed formula for $a_k$ otherwise the computation of chromatic polynomials would be very easy. Is $a_k$ known for a special class of graphs? I think that if the chromatic polynomial is known than we can derive $a_k$ by identification since the coefficients of a polynomial are unique, is that possible ? Thank you for your help ! 
 A: Once you have the chromatic polynomial, you can use the formula
$$
   ch(G,q) = \sum_{k=1}^n a_k(G) q(q-1)(\dots)(q-k+1)
$$
to find $a_1, a_2, a_3, \dots$ recursively. The key idea is that when evaluating $ch(G,q)$ for an integer $q<n$, instead of summing over all $k$ from $0$ to $n$, it's enough to sum from $0$ to $q$, because all other terms will be $0$. As a result, you're given an equation relating $ch(G,q)$ to $a_1, a_2, \dots, a_q$, and if you already know $a_1, a_2, \dots, a_{q-1}$, you can solve for $a_q$.
For example, say that $G$ is the cycle $C_6$, with chromatic polynomial $f(q) = (q-1)^6+q-1$. Then:


*

*$f(1) = 0 = a_1$, so $a_1=0$. (We can't cover $C_6$ with one independent set.)

*$f(2) = 2 = 2a_2 + 2a_1$; we know $a_1 = 0$, so $2 = 2a_2 + 0$, which means $a_2 = 1$. (There is one way to partition $C_6$ into two independent sets: even vertices and odd vertices.)

*$f(3) = 66 = 6a_3 + 6a_2 + 3a_1$; we know $a_1 = 0$ and $a_2 = 1$, so $66 = 6a_3 + 6 + 0$, which means $a_3 = 10$.

*$f(4) = 732 = 24a_4 + 24a_3 + 12a_2 + 4a_1$; we know $a_1 = 0, a_2 = 1, a_3 = 10$, so $732 = 24a_4 + 240+12+0$, which means $a_4 = 20$.

*And so on...



You're not going to be able to do better than this in general, because having a simple formula for $a_k(G)$ would give us a simple formula for $ch(G,q)$. However, if you just wanted to know $a_k(G)$ for a single value of $k$, it might make sense to use the same deletion-contraction approach that you us for finding the chromatic polynomial of $G$. 
Let $uv$ be any edge of $G$. Then $G-uv$ has all the same $k$-independent set decompositions as $G$ does, plus a bunch of invalid decompositions where $u$ and $v$ are in the same independent set. The number of these is exactly the number of decompositions of $G / uv$ (the graph we get by contracting edge $uv$). So we have
$$
   a_k(G) = a_k(G-uv) - a_k(G / uv).
$$
This is essentially the same computation you'd do for $ch(G,q)$ (Proposition 1.3 in the writeup you linked to), but you might be able to stop the recursion earlier. For example, for any $k$-vertex graph $G$, $a_k(G) = 1$, because the only valid decomposition is to put every vertex into its own independent set.
