{
  "id": "1409.7535",
  "version": "v1",
  "published": "2014-09-26T11:19:09.000Z",
  "updated": "2014-09-26T11:19:09.000Z",
  "title": "Acyclic Colorings of Directed Graphs",
  "authors": [
    "Noah Golowich"
  ],
  "comment": "14 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The acyclic chromatic number of a directed graph $D$, denoted $\\chi_A(D)$, is the minimum positive integer $k$ such that there exists a decomposition of the vertices of $D$ into $k$ disjoint sets, each of which induces an acyclic subgraph. For any $m \\geq 1$, we introduce a generalization of the acyclic chromatic number, namely $\\chi_m(D)$, which is the minimum number of sets into which the vertices of a digraph can be partitioned so that each set is weakly $m$-degenerate. We show that for all digraphs $D$ without directed 2-cycles, $\\chi_m(D) \\leq \\frac{4\\bar{\\Delta}(D)}{4m+1} + o(\\bar{\\Delta}(D))$. Because $\\chi_1(D) = \\chi_A(D)$, we obtain as a corollary that $\\chi_A(D) \\leq \\frac{4}{5} \\cdot \\bar{\\Delta}(D) + o(\\bar{\\Delta}(D))$, significantly improving a bound of Harutyunyan and Mohar.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-26T11:19:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C20"
    ],
    "keywords": [
      "directed graph",
      "acyclic colorings",
      "acyclic chromatic number",
      "disjoint sets",
      "acyclic subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.7535G"
    }
  }
}