Questions tagged [graph-polynomials]

Questions related to polynomials associated to a graph. For example, the Tutte polynomial, flow polynomial and chromatic polynomial.

Filter by
Sorted by
Tagged with
9 votes
5 answers
2k views

How many Tutte polynomials of complete graphs are known?

I would like to compute the Tutte polynomial of the complete graph $K_n$ for n as large as possible. Using a program by Björklund, Husfeldt, Kaski, Koivisto (here), I managed to compute up to n=18 on ...
Douglas S. Stones's user avatar
4 votes
1 answer
242 views

Do right-profiles determine graphs up to isomorphism?

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...
András Salamon's user avatar