Bipartite bithreshold graphs
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.
scientific article; zbMATH DE number 444642
scientific article