{
  "id": "1803.08658",
  "version": "v2",
  "published": "2018-03-23T05:42:00.000Z",
  "updated": "2020-07-10T03:27:21.000Z",
  "title": "Proof of Lundow and Markström's conjecture on chromatic polynomials via novel inequalities",
  "authors": [
    "Fengming Dong",
    "Jun Ge",
    "Helin Gong",
    "Bo Ning",
    "Zhangdong Ouyang",
    "Eng Guan Tay"
  ],
  "comment": "20 pages, 23 references. Accepted by J. Graph Theory",
  "categories": [
    "math.CO"
  ],
  "abstract": "The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\\sum\\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$, where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $\\epsilon(G)=\\sum\\limits_{i=1}^n (n-i)a_i/\\sum\\limits_{i=1}^n a_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markstr\\\"{o}m in 2006 that $\\epsilon(T_n)< \\epsilon(G)<\\epsilon(K_n)$ holds for any connected graph $G$ of order $n$ which is neither the complete graph $K_n$ nor a tree $T_n$ of order $n$. The most crucial step of our proof is to obtain the interpretation of all $a_i$'s by the number of acyclic orientations of $G$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2020-07-10T03:27:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C31",
      "05C20"
    ],
    "keywords": [
      "chromatic polynomial",
      "novel inequalities",
      "markströms conjecture",
      "broken-cycle free spanning subgraphs",
      "broken-cycle-free spanning subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}