A note on the shameful conjecture |
| |
Affiliation: | Department of Mathematics, Harvard University, One Oxford Street, Cambridge, MA 02138, United States |
| |
Abstract: | Let denote the chromatic polynomial of a graph on vertices. The ‘shameful conjecture’ due to Bartels and Welsh states that, Let denote the expected number of colors used in a uniformly random proper -coloring of . The above inequality can be interpreted as saying that , where is the empty graph on nodes. This conjecture was proved by F.M. Dong, who in fact showed that, for all . There are examples showing that this inequality is not true for all . In this paper, we show that the above inequality holds for all , where is the largest degree of . It is also shown that the above inequality holds true for all when is a claw-free graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|