Lowest Coefficient of Chromatic Polynomial

418 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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.