17
$\begingroup$

Given a graph $G$ on $n$ vertices, its chromatic polynomial $P(G,x)$ is a function that gives the number of proper colorings of G using $x$ colors.

When $P(G,x)$ is written using the basis $\{x, \ldots , x^n\}$, it is known that the coefficients of $x, \ldots , x^n$ alternate in signs; when $P(G,x)$ is written using the basis $\{ (x)_0, (x)_1, \ldots, (x)_n \}$, where $(x)_k = x(x-1)(x-2) \cdot \ldots \cdot (x-(k-1))$ denotes the falling factorial, then its coefficients are nonnegative.

I verified at SageMath that, up to $9$ vertices, when $P(G,x)$ is written using the basis $\{ x^{n-1}(x)_1, x^{n-2}(x)_2, \ldots, (x)_n \}$, then its coefficients are also nonnegative, but I could not find an example of graph with at least one negative coefficient and I have not found any proof of this fact in the literature.

Is anyone aware of this result? This question arises from work in progress by Petter Brändén and Leonardo Saud.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Careful that $x^n(x)_0=x^{n-1}(x)_1$. $\endgroup$
    – Abdelmalek Abdesselam
    Commented Sep 16 at 17:33
  • $\begingroup$ Oh, yes! You are correct. Fixed now :) $\endgroup$
    – ls1995
    Commented Sep 16 at 17:40
  • $\begingroup$ Maybe I'm missing something, but wouldn't this follow from induction on the deletion-contraction recurrence? Reordering the formula gives $P(G-uv,k)=P(G,k)+P(G/uv,k)$, and if $G$ has $n$ vertices then $G/uv$ has $n-1$ vertices, thus has nonnegative coefficients by the induction assumption. So deleting edges cannot decrease the coefficients of the chromatic polynomial in that basis. Since any graph can be obtained by starting from a complete graph (with polynomial $(x)_n$) and deleting some edges, we are done. $\endgroup$
    – pregunton
    Commented Sep 16 at 19:36
  • 5
    $\begingroup$ @pregunton For an $n$ vertex graph, every polynomial in the basis has degree $n$. So the basis polynomials are different for an $n-1$ vertex graph, $\endgroup$
    – Gordon Royle
    Commented Sep 16 at 19:50
  • $\begingroup$ @GordonRoyle Oh, sorry, you're right, I didn't read the question properly. $\endgroup$
    – pregunton
    Commented Sep 16 at 19:54

1 Answer 1

Reset to default
8
$\begingroup$

In case anyone stumbles across this question, the statement (that all the coefficients in this basis are non-negative) is not true.

The complete bipartite graph $K_{7,7}$ has the following coefficients in the given basis, where the third coefficient is negative.

                                            0]
[                                      1/4096]
[                            -11249/725594112]
[                      961739905/371504185344]
[         1043130571860013/241864704000000000]
[           395726588093431/20155392000000000]
[  23163981271533774127/553294399795200000000]
[168461889135965303089/1770542079344640000000]
[634055484774359381981/4097540240769024000000]
[    3111149918504247421/14634072288460800000]
[    3312627477466754807/15458690647572480000]
[          4914499543566463/30672005253120000]
[              13048613951497/172613016576000]
[                        116914351/6227020800]

I am aware that this is difficult for a third-party to check, but the counterexample has been confirmed by the originators of the question.

Improve this answer
$\endgroup$

You must log in to answer this question.

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