{
  "id": "1202.5718",
  "version": "v1",
  "published": "2012-02-26T02:58:23.000Z",
  "updated": "2012-02-26T02:58:23.000Z",
  "title": "Chordal Graphs are Fully Orientable",
  "authors": [
    "Hsin-Hao Lai",
    "Ko-Wei Lih"
  ],
  "comment": "11 pages, 1 figure, accepted by Ars Combinatoria (March 26, 2010)",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying m <= d <= M. A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-02-26T02:58:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99"
    ],
    "keywords": [
      "chordal graphs",
      "fully orientable",
      "acyclic orientation",
      "dependent arcs",
      "reversal creates"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1202.5718L"
    }
  }
}