# Tutte polynomial from independent sets of a graph

Let $G$ be a connected graph with chromatic polynomial $X(G,q)$. Since $k$-proper coloring a graph is same as partitioning the vertex set $V$ into $k$ independent sets (a subset of the vertex set in which no two vertices are adjacent) (we call this $k$-independent partition), the chromatic polynomial can be retrieved if we know all the independent subsets of $V$. For example, we have the following expression:

$$X(G,q) = \sum_{k \ge 1} \binom{q}{k} C_k(G)$$ where $C_k(G)$ is the number of number of $k$-independent partitions of $V$.

My question is, is there such a nice expression (fully in terms of independent sets) for Tutte polynomial?

Thank you.

• I don't think the question you have asked is the question you meant to ask. If you know all the independent sets of the graph, then you know all its non-edges and so you actually know the graph. – Gordon Royle Sep 9 '18 at 13:45
• @GordonRoyle Thanks. I have edited the question. – GA316 Sep 10 '18 at 3:47
• I think the answer must be “no” because if it were so, two chromatically equivalent graphs would be Tutte equivalent, which is certainly not true. – Gordon Royle Sep 10 '18 at 8:27