A Characterization of Signed Graphs with Generalized Perfect Elimination Orderings
arXiv:0712.4118
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.
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