pith. sign in

arxiv: 1502.06032 · v1 · pith:FVV3G2USnew · submitted 2015-02-20 · 🧮 math.CO

A note on the shameful conjecture

classification 🧮 math.CO
keywords fracinequalityaboveconjecturegraphdenoteholdsshameful
0
0 comments X
read the original 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, $$\frac{P_G(n)}{P_G(n-1)} \geq \frac{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) \geq \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, $$\frac{P_G(q)}{P_G(q-1)} \geq \frac{q^n}{(q-1)^n}$$ for all $q \geq n$. There are examples showing that this inequality is not true for all $q \geq 2$. In this paper, we show that the above inequality holds for all $q \geq 36D^{3/2}$, where $D$ is the largest degree of $G$. It is also shown that the above inequality holds true for all $q \geq 2$ when $G$ is a claw-free graph.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.