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?

Please share your thoughts.

Thank you.

  • 2
    $\begingroup$ 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. $\endgroup$ – Gordon Royle Sep 9 '18 at 13:45
  • $\begingroup$ @GordonRoyle Thanks. I have edited the question. $\endgroup$ – GA316 Sep 10 '18 at 3:47
  • 4
    $\begingroup$ 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. $\endgroup$ – Gordon Royle Sep 10 '18 at 8:27

Your Answer

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

Browse other questions tagged or ask your own question.