{
  "id": "2111.02352",
  "version": "v2",
  "published": "2021-11-03T17:07:21.000Z",
  "updated": "2022-01-30T14:44:56.000Z",
  "title": "An Improved Bound of Acyclic Vertex-Coloring",
  "authors": [
    "Lefteris Kirousis",
    "John Livieratos"
  ],
  "comment": "The previous to the last sentence of Section 4, namely that \"This means that $\\hat{Q}$ and, by Lemma 6, $\\hat{Q}$ too, is less than 1.\" is wrong",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The acyclic chromatic number of a graph is the least number of colors needed to properly color its vertices so that none of its cycles has only two colors. We show that for all $\\alpha>2^{-1/3}$ there exists an integer $\\Delta_{\\alpha}$ such that if the maximum degree $\\Delta$ of a graph is at least $\\Delta_{\\alpha}$, then the acyclic chromatic number of the graph is at most $\\lceil\\alpha {\\Delta}^{4/3} \\rceil +\\Delta+ 1$. The previous best bound, due to Gon\\c{c}alves et al (2020), was $(3/2) \\Delta^{4/3} + O(\\Delta)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-01-30T14:44:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "G.2.2"
    ],
    "keywords": [
      "acyclic vertex-coloring",
      "acyclic chromatic number",
      "best bound",
      "maximum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}