{
  "id": "0712.4118",
  "version": "v3",
  "published": "2007-12-26T10:24:43.000Z",
  "updated": "2009-02-03T15:18:33.000Z",
  "title": "A Characterization of Signed Graphs with Generalized Perfect Elimination Orderings",
  "authors": [
    "Koji Nuida"
  ],
  "comment": "18 pages; (v2) Reference updated (v3) Major update including title change, shortening of proof of main theorem, addition of applications of main theorem to special cases, reference update",
  "journal": "Discrete Mathematics vol.310, no.4 (2010) 819-831",
  "categories": [
    "math.CO",
    "math.AG"
  ],
  "abstract": "An important property of chordal graphs is that these graphs are characterized by existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2009-02-03T15:18:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "05C15",
      "52C35"
    ],
    "keywords": [
      "generalized perfect elimination orderings",
      "signed graphs",
      "characterization",
      "important property",
      "chordal graphs"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0712.4118N"
    }
  }
}