{
  "id": "1102.1021",
  "version": "v2",
  "published": "2011-02-04T21:43:04.000Z",
  "updated": "2011-08-08T15:19:18.000Z",
  "title": "An improvement on Brooks' Theorem",
  "authors": [
    "Landon Rabern"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that $\\chi(G) \\leq \\max {\\omega(G), \\Delta_2(G), (5/6)(\\Delta(G) + 1)}$ for every graph $G$ with $\\Delta(G) \\geq 3$. Here $\\Delta_2$ is the parameter introduced by Stacho that gives the largest degree that a vertex $v$ can have subject to the condition that $v$ is adjacent to a vertex whose degree is at least as large as its own. This upper bound generalizes both Brooks' Theorem and the Ore-degree version of Brooks' Theorem.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-08-08T15:19:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "improvement",
      "upper bound generalizes",
      "largest degree",
      "ore-degree version"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1102.1021R"
    }
  }
}