# Graphical representation of chromatic polynomial

Suppose $c(G,u)$ is chromatic polynomial of connected simple graph $G$. We know that $|c(G,-1)|$, as Stanley proved, is the total number of directed graph on $G$, without any cycle. Also, we know some other graphical representations of the value of $c(G,u)$.

1) Do we have any graphical representation for $|c(G,2)|$?

2) Do we have any graphical representation for the multiplicity of $2$ as a root of $c(G,u)$?

I found some graphical representation for these values, but I didn't prove them yet.

-
$c(G(2))$ is always non-negative and equals 0 for non-bipartite graphs and $2^m$ for bipartite graphs with $m$ components, this clearly follows from the definition of chromatic polynomial. As for your second question, it looks challenging (the answers for multiplicities of 0 and 1 count number of connected components and two-connected blocks respectively, so the multiplicity of 2 seems to be the interesting invariant). – Fedor Petrov Jan 1 '12 at 21:15
Do we have any proof for your second answer? Do you know any reference about this question? It is interesting that, for Fan graph($F_n$, the multiplicity of 2 is $n$ and the number of blocks is exactly $n$. But in general, we can't interpret the multiplicity of 2 by only the number of $blocks$. – Shahrooz Janbaz Jan 2 '12 at 9:18
The multiplicity is clearly additive along the operation of gluing two graphs along a common vertex, so it's the sum, over the 2-connected blocks, of some function. More generally, the multiplicity of $n$ is additive under the operation of gluing two graphs along a common $K_n$, $n\leq k$, so you can also consider just 2-connected graphs that have no $K_2$ cutset. – Will Sawin Jan 2 '12 at 22:27
What is $k$? Is it the number of vertices of predefined graph? Do you have good references about these topics? – Shahrooz Janbaz Jan 3 '12 at 18:58

As the multiplicity of 0 is the number of connected components of a graph, and for a connected graph the multiplicity of 1 is the number of blocks, then we might hope that for a 2-connected graph, the multiplicity of "2" would be related to the number of 3-connected "parts" (in some sense).

However if this was true in any sensible fashion, then a 3-connected graph would have "2" occurring with multiplicity one and this does not happen - there are 3-connected graphs that do not satisfy this.

On the other hand, I feel that there must be SOME combinatorial interpretation, though perhaps only valid for some graphs.

Edit: I looked up some of my old emails and notes and have the following conjecture, inspired by a related conjecture of Dong:

If $G$ is a 3-connected graph such that for any independent vertex-cutset $S$, the number of components of $G-S$ is no larger than $|S|$ then $2$ is a single root of the chromatic polynomial.

-
Dear Gordon Thank you for your answer. Because of your answer, this problem might be open still now, yes? I found a graphical representation for multiplicity of "2" as a root of chromatic polynomial. I tested it for different graphs and it is true. But, I need some tools and techniques to attack to this problem. Can you introduce me some references for studying and gathering some techniques related to this problem? I will be so appreciate. – Shahrooz Janbaz Jan 5 '12 at 9:13
Yes, I would say it is open. There are many resources for basic chromatic polynomial theory - try Dong, Koh and Teo's book "Chromatic Polynomials and Chromaticity of Graphs" for a comprehensive recent treatment. Dong is one of the main players in this area. – Gordon Royle Jan 5 '12 at 12:21
Thank you very much for your guidance. Sincerely – Shahrooz Janbaz Jan 5 '12 at 13:20