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.

Improve this question
$\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$
    – Fedor Petrov
    Commented 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
    Commented 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
    Commented 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
    Commented Jan 3, 2012 at 18:58

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Gordon Royle
    Commented Jan 5, 2012 at 12:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .