{
  "id": "2401.15130",
  "version": "v1",
  "published": "2024-01-26T15:15:01.000Z",
  "updated": "2024-01-26T15:15:01.000Z",
  "title": "Dichromatic Number and Cycle Inversions",
  "authors": [
    "Pierre Charbit",
    "Stéphan Thomassé"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The results of this note were stated in the first author PhD manuscript in 2006 but never published. The writing of a proof given there was slightly careless and the proof itself scattered across the document, the goal of this note is to give a short and clear proof using Farkas Lemma. The first result is a characterization of the acyclic chromatic number of a digraph in terms of cyclic ordering. Using this theorem we prove that for any digraph, one can sequentially reverse the orientations of the arcs of a family of directed cycles so that the resulting digraph has acyclic chromatic number at most 2.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-01-26T15:15:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C20",
      "G.2.2"
    ],
    "keywords": [
      "dichromatic number",
      "cycle inversions",
      "acyclic chromatic number",
      "first author phd manuscript",
      "clear proof"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}