1
$\begingroup$

For a simple graph $G$ on $n$ vertices, let ${\rm chr}(G,z)=\sum_{i=1}^n a_i z^i$ be the chromatic polynomial of $G$. I am interested in the coefficient $a_1$, that is, the coefficient on the linear term of ${\rm chr}(G,z)$. It is well-known that $a_1 \neq 0$ iff $G$ is connected. Also, for any $G$ we have $\left|a_1\right| \leq (n-1)!$, and for the complete graph we have $|a_1|=(n-1)!$. It therefore seems appropriate to say that $|a_1|$ is a "measure of connectivity" of $G$.

My first question is whether there is a characterization (or construction) of $|a_1 |$ that justifies this interpretation as a "measure of connectivity" of $G$ more generally (beyond the extreme cases of disconnected and complete graphs mentioned above).

My second question is whether $|a_1 |$ can be related to other graph connectivity measures like algebraic connectivity or the Cheeger constant.

$\endgroup$
3
  • $\begingroup$ Of course, the sign of $a_1$ is just $(-1)^{n+1}$, the question is about the absolute value $|a_1|$. $\endgroup$
    – MathSmith
    Nov 11 '16 at 18:55
  • $\begingroup$ Do you have a reference for the statement that $|a_1| \le (n-1)!$? I can prove it but I am unable to find it stated anywhere, and I am surprised that such an elementary fact would not be collected in any text on chromatic polynomials. $\endgroup$ Apr 10 '18 at 21:21
  • $\begingroup$ No, sorry, not aware of any reference for this. $\endgroup$
    – MathSmith
    Apr 12 '18 at 7:56
2
$\begingroup$

I do not know if this a satisfying answer in terms of characterization of $|a_1|$ as a measure of connectivity of the graph, but: $|a_1|$ is the number of acyclic orientations with one fixed source node.

In fact, $|a_1| = (-1)^{n-1} a_1$ is the evalutation of the Tutte polynomial of the graph at $(1,0)$, i.e. $T_G(1,0) = (-1)^{n-1} \frac{d}{dz} \mathrm{chr}(G,0)|_{z=0}$.

Then this characterization of $T_G(1,0)$ can be found in Theorem 8 of https://arxiv.org/abs/0803.3079 and references within.

$\endgroup$
1
  • $\begingroup$ This is very interesting, thank you, I did not know. This is probably the closest we can get to a "solution" of this question at this point. $\endgroup$
    – MathSmith
    Apr 16 '18 at 11:09
2
$\begingroup$

Nice question!

There are graphs that have the same linear coefficient and different vertex connectivity. For example the three graphs on the above figure all have $240$ as their linear term coefficient and their vertex connectivity are 2,3 and 4. There seem to be many such examples out there.enter image description here

IIRC the only other connectivity measure that one gets from the chromatic polynomial is the multiplicity of the root 1 which counts the number of blocks.

$\endgroup$
1
  • $\begingroup$ This is interesting. However, Cheeger's inequality provides a bound on the algebraic connectivity in terms of the Cheeger constant (and vice versa), but nevertheless we can find graphs with the same Cheeger constant and different algebraic connectivity. That is, the two "connectivity" measures are not one-to-one, but are nevertheless related. Something similar could be true for $|a_1|$ and other measures of connectivity. $\endgroup$
    – MathSmith
    Nov 13 '16 at 17:45

Your Answer

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

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