{
  "id": "1502.06032",
  "version": "v1",
  "published": "2015-02-20T23:05:24.000Z",
  "updated": "2015-02-20T23:05:24.000Z",
  "title": "A note on the shameful conjecture",
  "authors": [
    "Sukhada Fadnavis"
  ],
  "comment": "Accepted to the European Journal of Combinatorics",
  "doi": "10.1016/j.ejc.2015.02.001",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-02-20T23:05:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "shameful conjecture",
      "inequality holds true",
      "largest degree",
      "welsh states",
      "empty graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}