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 |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8844548463821411
0 references
0.8607988953590393
0 references
0.830128014087677
0 references
0.8301007747650146
0 references
0.8115711212158203
0 references
