𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chordal Bipartite Graphs with High Boxicity

✍ Scribed by L. Sunil Chandran; Mathew C. Francis; Rogers Mathew

Publisher
Springer Japan
Year
2011
Tongue
English
Weight
186 KB
Volume
27
Category
Article
ISSN
0911-0119

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

Chordal bipartite graphs and crowns
Chordal bipartite graphs and crowns
✍ Vincent BouchittΓ© πŸ“‚ Article πŸ“… 1985 πŸ› Springer Netherlands 🌐 English βš– 178 KB
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