A note on the shameful conjecture

Let PG(q)PG(q) denote the chromatic polynomial of a graph GG on nn vertices. The ‘shameful conjecture’ due to Bartels and Welsh states that, PG(n)PG(n−1)≥nn(n−1)n. Let μ(G)μ(G) denote the expected number of colors used in a uniformly random proper nn-coloring of GG. The above inequality can be interpreted as saying that μ(G)≥μ(On)μ(G)≥μ(On), where OnOn is the empty graph on nn nodes. This conjecture was proved by F.M. Dong, who in fact showed that, PG(q)PG(q−1)≥qn(q−1)n for all q≥nq≥n. There are examples showing that this inequality is not true for all q≥2q≥2. In this paper, we show that the above inequality holds for all q≥36D3/2q≥36D3/2, where DD is the largest degree of GG. It is also shown that the above inequality holds true for all q≥2q≥2 when GG is a claw-free graph.