Bipartite bithreshold graphs (Q688258)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Bipartite bithreshold graphs |
scientific article; zbMATH DE number 444642
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bipartite bithreshold graphs |
scientific article; zbMATH DE number 444642 |
Statements
Bipartite bithreshold graphs (English)
0 references
26 June 1994
0 references
This paper deals with bithreshold graphs and their characterization. After having given some necessary properties the authors succeed in proving a complete characterization of the class of bipartite bithreshold graphs by means of 11 not bithreshold (so-called forbidden induced subgraphs) and 5 classes of induced subgraphs. The proof is very tricky and beautiful. The authors conclude by presenting an \(O(n^ 2)\)- algorithm for recognizing bipartite bithreshold graphs.
0 references
bithreshold graphs
0 references
0 references
