Back to Search
Start Over
A note on the shameful conjecture.
- Source :
-
European Journal of Combinatorics . Jul2015, Vol. 47, p115-122. 8p. - Publication Year :
- 2015
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 47
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 108341823
- Full Text :
- https://doi.org/10.1016/j.ejc.2015.02.001