1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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
    Commented Feb 1, 2019 at 6:49

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. I have some doubts. Is it possible to extract the number of edges between the vertices from Tutte polynomial? $\endgroup$
    – GA316
    Commented Feb 2, 2019 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
    Commented Feb 2, 2019 at 8:25
  • 2
    $\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
    Commented Feb 6, 2019 at 18:21
  • 2
    $\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
    Commented Feb 6, 2019 at 18:28
  • $\begingroup$ @AaronDall similarly, can we read the number of (multi)edges between two particular vertices $u$ and $v$ of $G$ from $T$? $\endgroup$
    – GA316
    Commented Feb 18, 2022 at 2:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .