Are there some researches about upper bound of number of k-coloring of a graph with n vertices and m edges?

14 Views Asked by At

Let $G$ be a graph with $n$ vertices and $m$ edges, and $A_k(G)$ be the number of $k$-coloring of $G$. If there is a matching $M$ of $G$ with $|M|=t$, then it is clear that $A_k(G)\leq (k^2-k)^{t}k^{n-2t}$. So it is possible to give a upper bound of $A_k(G)$ about $n,m$. Are there some results about this?