Premium
Perfect Elimination and Chordal Bipartite Graphs
Author(s) -
Golumbic Martin Charles,
Goss Clinton F.
Publication year - 1978
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190020209
Subject(s) - chordal graph , mathematics , combinatorics , bipartite graph , strong perfect graph theorem , indifference graph , discrete mathematics , diagonal , 1 planar graph , graph , geometry
We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal.