Koji Nuida
Published 2007-12-26, updated 2009-02-03Version 3
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.
Comments: 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
A characterization of Tutte-Coxeter graph
Characterization of Cobweb Posets as KoDAGs
The Characterization of planar, 4-connected, K_{2,5}-minor-free graphs
![QR code for arXiv:0712.4118 [math.CO]](http://oss.arxitics.com/images/favicon.svg)