𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Classes of bipartite graphs related to chordal graphs

✍ Scribed by Andreas Brandstädt

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
631 KB
Volume
32
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Treewidth of Chordal Bipartite Graphs
Treewidth of Chordal Bipartite Graphs
✍ T. Kloks; D. Kratsch 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 743 KB

Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one. We present a polynomial time algorithm for the exact computa

Perfect Elimination and Chordal Bipartit
Perfect Elimination and Chordal Bipartite Graphs
✍ Martin Charles Golumbic; Clinton F. Goss 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## Abstract 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 spars

Hamiltonian circuits in chordal bipartit
Hamiltonian circuits in chordal bipartite graphs
✍ Haiko Müller 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 359 KB

The main result of this paper is the NP-completeness of the HAMILTONIAN CIRCUIT problem for chordal bipartite graphs. This is proved by a sophisticated reduction from SATISFIABILITY. As a corollary, HAMILTONIAN CIRCUIT is NP-complete for strongly chordal split graphs. On both classes the complexity