A note on the shameful conjecture

Abstract

Let $P_G(q)$ denote the chromatic polynomial of a graph $G$ on $n$ vertices. The `shameful conjecture' due to Bartels and Welsh states that, $$\frac{P_G(n)}{P_G(n-1)}\ge \frac{n^n}{(n-1{)}^n}.$$ Let $\mu (G)$ denote the expected number of colors used in a uniformly random proper $n$-coloring of $G$. The above inequality can be interpreted as saying that $\mu (G)\ge \mu (O_n)$, where $O_n$ is the empty graph on $n$ nodes. This conjecture was proved by F. M. Dong, who in fact showed that, $$\frac{P_G(q)}{P_G(q-1)}\ge \frac{q^n}{(q-1{)}^n}$$ for all $q\ge n$. There are examples showing that this inequality is not true for all $q\ge 2$. In this paper, we show that the above inequality holds for all $q\ge 36D^{3/2}$, where $D$ is the largest degree of $G$. It is also shown that the above inequality holds true for all $q\ge 2$ when $G$ is a claw-free graph.

Accepted to the European Journal of Combinatorics