{
  "id": "1308.6739",
  "version": "v3",
  "published": "2013-08-30T13:32:21.000Z",
  "updated": "2014-08-27T10:29:58.000Z",
  "title": "Beyond Ohba's Conjecture: A bound on the choice number of $k$-chromatic graphs with $n$ vertices",
  "authors": [
    "Jonathan A. Noel",
    "Douglas B. West",
    "Hehui Wu",
    "Xuding Zhu"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $\\text{ch}(G)$ denote the choice number of a graph $G$ (also called \"list chromatic number\" or \"choosability\" of $G$). Noel, Reed, and Wu proved the conjecture of Ohba that $\\text{ch}(G)=\\chi(G)$ when $|V(G)|\\le 2\\chi(G)+1$. We extend this to a general upper bound: $\\text{ch}(G)\\le \\max\\{\\chi(G),\\lceil({|V(G)|+\\chi(G)-1})/{3}\\rceil\\}$. Our result is sharp for $|V(G)|\\le 3\\chi(G)$ using Ohba's examples, and it improves the best-known upper bound for $\\text{ch}(K_{4,\\dots,4})$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-10-01T18:48:22.000Z",
      "abstract": "Noel, Reed, and Wu proved the conjecture of Ohba stating that the choice number of a graph $G$ equals its chromatic number when $|V(G)|\\le 2\\chi(G)+1$. We extend this to a general upper bound: \\[\\ch(G)\\le \\max\\left\\{\\chi(G),\\left\\lceil\\frac{|V(G)|+\\chi(G)-1}{3}\\right\\rceil\\right\\}.\\] For $|V(G)|\\le 3\\chi(G)$, Ohba provided examples where equality holds.",
      "comment": "13 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-08-27T10:29:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "choice number",
      "ohbas conjecture",
      "chromatic graphs",
      "general upper bound",
      "chromatic number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.6739N"
    }
  }
}