A note on the shameful conjecture. (July 2015)

• Record Type: Journal Article
• Authors: Fadnavis, Sukhada
• Is Part Of: European journal of combinatorics. Volume 47(2015:Jul.)
• Page Start: 115
• Page End: 122
• Publication Date: 2015-07
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.02.001
• Languages: English
• ISSNs: 0195-6698

Abstract

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, P G ( n ) P G ( n − 1 ) ≥ n n ( n − 1 ) n . Let μ ( 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 μ ( G ) ≥ μ ( 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 ≥ 36 D 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.