Let $G$ be a multigraph, i.e, there can be more than one edge between a pair of vertices. It is clear that the chromatic polynomial cannot capture these multi-edges. Because chromatic polynomial just cares whether two vertices are adjacent or not and doesn't care about the number of edges between them.

My question: is there any combinatorial tool like chromatic polynomial which captures the number of edges between the vertices as well?

Kindly share your thoughts.

Thank you.

  • 1
    $\begingroup$ Tutte polynomial? It's specialisation is the chromatic polynomial, but in general it relies very much on multiple edges. You may use equivalent "bichromatic polynomial" approach to Tutte polynomial, which is even more directly generalisation if the chromatic polynomial. $\endgroup$ – Fedor Petrov Feb 1 at 6:49

I think that the Tutte polynomial, as suggested by Fedor Petrov in the comments, is likely what you are looking for. For a graph $G$, this is the polynomial $$ T(x, y) = \sum_{A \subseteq E(G)} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V(G)|}$$ where $k(A)$ is the number of connected components of $(V(G), A)$. Indeed, the Tutte polynomial is well defined for any matroid, including the graphic matroid $M(G)$ induced by any graph $G$, and in this case equals the above polynomial. There is no restriction on $G$ not being a multigraph in either of these two definitions.

The primary reason why it generalizes the chromatic polynomial for a graph is due to the fact that evaluation at $y=0$ of the Tutte polynomial is closely related to the chromatic polynomial. More specifically, $$ \chi_G(\lambda) = (-1)^{|V(G)| - k(G)} \lambda^{k(G)} T_G(1 - \lambda, 0)$$ In fact, just as deletion-contraction holds for the chromatic polynomial, it too does for the Tutte polynomial. The above specialization to the chromatic polynomial is only one of many of the Tutte polynomial, and there is a great deal of interesting material to be found online regarding it.

  • $\begingroup$ Thank you. I have some doubts. Is it possible to extract the number of edges between the vertices from Tutte polynomial? $\endgroup$ – GA316 Feb 2 at 6:18
  • 2
    $\begingroup$ The value $T(2,2)$ is $2^n$ where $n$ is the total number of edges in the graph. $\endgroup$ – Aaron Dall Feb 2 at 8:25
  • 1
    $\begingroup$ Alternatively, you may consider the bichromatic polynomial $Z(q, s) =\sum (1+s)^{m}$, where the summation is over all (not only proper) colourings of vertices with $q$ colors, $m$ is the number of not properly colored edges. $\endgroup$ – Fedor Petrov Feb 6 at 18:21
  • 1
    $\begingroup$ (cont.) it clearly generalizes the chromatic polynomial and clearly relies on the multiplicities of edges. The connection with Tutte polynomial $T(x, y) $ is via the change of variables $s=y-1,q=(x-1)(y-1)$. $T(x, y) =q^{-r}s^{r-N} Z(q, s) $, where $r$ is the number of connected components and $n$ the number of vertices. $\endgroup$ – Fedor Petrov Feb 6 at 18:28

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.