Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then $$\bigcup_G \big\{z \in \mathbb{C}:P(G;z)=0\big\}$$ is a dense subset of $\mathbb{C}$. Generalizing this...

Question: Is, for all fixed $c \in \mathbb{C}$, $$\bigcup_G \big\{z \in \mathbb{C}:P(G;z)=c\big\}$$ is a dense subset of $\mathbb{C}$?


  • For any $c$, the subset will be a countable subset of $\mathbb{C}$.

  • It doesn't seem straightforward to edit a graph $G$ with chromatic root $z$, to give a graph $G'$ with $P(G';z)=c$. (Although, maybe I'm missing something.) This would rule out an obvious approach. (It still might be possible to modify Sokal's method to find an answer, but this would be lengthy.)

  • Real chromatic roots are not dense in $\mathbb{R}$. So probably there's a big difference between the two cases ($\mathbb{C}$ and $\mathbb{R}$) here too.

  • 2
    $\begingroup$ I wonder, is there some natural family of polynomials, where the roots are dense in $\mathbb{C}$, but the roots of $P(z)-c$ are not dense... $\endgroup$ May 23 '14 at 7:49
  • $\begingroup$ The question is asked for fixed constants $c \in \mathbb{C}$. Is it clearly true restricting to weaker cases, such as $\mathbb{R}$ or $\mathbb{Q}$? Relatedly, suppose you start with a finite simple graph $G$, and you add $c \in \mathbb{Z}^{+}$ vertices - connect each of them to one another, and then connect each of them to the vertices in $G$ - to produce a new graph $G'$. If $P(G;z) = 0$, is it true that $P(G';z) = c$? $\endgroup$ May 23 '14 at 8:51
  • $\begingroup$ Consider the set $U$ of all $c \in \mathbb{C}$ for which your set is dense. I wonder: can we argue naively that $U$ is closed? Open? $\endgroup$ May 24 '14 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.