A note on the shameful conjecture

作者：Fadnavis Sukhada^*

来源：European Journal of Combinatorics, 2015, 47: 115-122.

DOI：10.1016/j.ejc.2015.02.001

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,
P-G(n)/P-G(n - 1) >= 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) >= 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,
P-G(q)/P-G(q - 1) >= q(n)/(q - 1)(n)
for all q >= n. There are examples showing that this inequality is not true for all q >= 2. In this paper, we show that the above inequality holds for all q >= 36D(3/2), where D is the largest degree of G. It is also shown that the above inequality holds true for all q >= 2 when G is a claw-free graph.

• 出版日期2015-7