3
$\begingroup$

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.

Thanks for any helpful answer and good references.

$\endgroup$
4
  • 4
    $\begingroup$ $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). $\endgroup$ Jan 1, 2012 at 21:15
  • $\begingroup$ 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$. $\endgroup$
    – Shahrooz
    Jan 2, 2012 at 9:18
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Jan 2, 2012 at 22:27
  • $\begingroup$ What is $k$? Is it the number of vertices of predefined graph? Do you have good references about these topics? $\endgroup$
    – Shahrooz
    Jan 3, 2012 at 18:58

1 Answer 1

3
$\begingroup$

The answer to your second question appears to be "no".

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Shahrooz
    Jan 5, 2012 at 9:13
  • $\begingroup$ 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. $\endgroup$ Jan 5, 2012 at 12:21

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.