A Characterization of Edge-Bicolored Graphs with Generalized Perfect Elimination Orderings
Koji Nuida · arXiv (Cornell University) · 2007
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 graphs with edge-colorings by two colors, and give an excluded-subgraph characterization for graphs with such orderings. As an application, we announce some forthcoming results on hyperplane arrangements which can be derived from our result in this paper. Key words: graph; edge-colored graph; chordal graph; perfect elimination ordering; generalization; excluded-subgraph characterization; hyperplane arrangement 2 1