A characterization of signed graphs with generalized perfect elimination orderings

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


An important property of chordal graphs is that these graphs are characterized by the 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. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal.

Original languageEnglish
Pages (from-to)819-831
Number of pages13
JournalDiscrete Mathematics
Issue number4
Publication statusPublished - Feb 28 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A characterization of signed graphs with generalized perfect elimination orderings'. Together they form a unique fingerprint.

Cite this