I was playing around with the chromatic polynomial (denoted here by $\chi_G(x)$) and I have made the following conjecture.

Let $(G_n)_{n \ge 1}$ be a sequence of graphs with $v(G_n) \to \infty$ ($v(G_n)$ denotes the number of vertices of $G_n$) and $e(G_n) \to \infty$ ($e(G_n)$ denotes the number of edges of $G_n$).

For each $x \neq 0$, let us define the following transform of the chromatic polynomial of $G_n$ $$ \psi_{G_n}(x) = \frac{x^{v(G_n)}}{e(G_n)^{v(G_n)}} \chi_{G_n}\left( \frac{e(G_n)}{x} \right). $$

The conjecture is that for each fixed real number $x \neq 0$, we have $\psi_{G_n}(x) \to \exp(-x)$ as $n$ goes to infinity.

I have checked the conjecture for a few sequences of graphs: for example, $G_n$ being the complete graph $K_n$, for $G_n$ being a tree on $n$ vertices and for $G_n$ being a collection of $n$ independent edges (a matching on $2n$ vertices).

Does anyone know if this is well-known?

PS: I am not sure if the conditions on $v(G_n)$ and $e(G_n)$ are the right one. Any comments on this are welcome as well.

  • $\begingroup$ There doesn’t seem to anything in this problem that says “chromatic polynomial” as opposed to much a broader class of polynomials. $\endgroup$ Aug 16, 2020 at 9:02
  • 2
    $\begingroup$ Actually there's a heuristic justifying the equation when $k=e(G)/x$ is a natural number: Color the graph randomly with $k$ colors. If $k$ is large enough, the probability of the coloring being proper is close to $((k-1)/k)^{e(G)}$, so $\psi(x)$ is close to $((k-1)/k)^{kx}$. $\endgroup$ Aug 16, 2020 at 9:13
  • $\begingroup$ There are two limitations of the heuristic: the first is that one cannot modify $k$ without dealing with $G_n$ (this can be overcome by effective probability bounds), and the second is that $e(G)/x$ may not be a natural number, so the counting interpretation does not work. I would like to know counting-like interpretations of $χ$ at non-natural values. $\endgroup$ Aug 16, 2020 at 9:16
  • $\begingroup$ @LeechLattice The only non-natural for which a counting interpretation of $\chi$ is known seems to be $-1$, but any interpretation for a non-integer would be a major breakthrough. $\endgroup$ Aug 16, 2020 at 11:21
  • 4
    $\begingroup$ @GordonRoyle Though irrelevant to the problem, a counting interpretation of $\chi$ is known for every integer. $\endgroup$ Aug 16, 2020 at 17:46

1 Answer 1


Here is a heuristic argument which perhaps someone can make rigorous. I write $v_n=v(G_n)$ and $e_n=e(G_n)$. Let $$ \chi_{G_n}(x) = x^{v_n}-c_{n,v_n-1} x^{v_n-1}+c_{n,v_n-2}x^{v_n-2}-\cdots. $$ I claim that for fixed $k\geq 0$, $$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$ One can prove this by noting that (by the Broken Circuit Theorem, for instance, which shows that $c_{n,v_n-k}$ increases as we add more edges to $G_n$) $c_{n,v_n-k}$ is bounded below by its value when $G_n$ is a tree, and is bounded above by its value when $G_n$ is a complete graph. The claimed result is easily verified for trees and complete graphs (in the latter case, using known asymptotics for the Stirling numbers of the first kind). Perhaps there is a more direct proof, but in any case, if we don't worry about justifying interchanging limits and sums, we get $$ \lim_{n\to\infty} \frac{x^{v_n}}{e_n^{v_n}}\chi_{G_n}\left( \frac{e_n}{x}\right) = \sum_{k\geq 0} \lim_{n\to\infty} \frac{(-1)^k c_{n,v_n-k}x^k}{e_n^k} $$ $$ \qquad = \sum_{k\geq 0} \frac{(-1)^k x^k}{k!} = \exp(-x). $$

  • $\begingroup$ That's exactly what I was thinking with a friend earlier today. Thank you! $\endgroup$
    – mtsecco
    Aug 16, 2020 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.