Bipartite bithreshold graphs
type: Item
instance of: scholarly article
title: Bipartite bithreshold graphs
zbMATH Open document ID: 0790.05082
DOI: 10.1016/0012-365X(93)90118-D
author: Peter L. Hammer
author: N. V. R. Mahadev
author: Uri N. Peled
published in: Discrete Mathematics
publication date: 1994-06-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 444642
zbMATH Keywords: bithreshold graphs
reviewed by: Rainer Bodendiek
MaRDI profile type: MaRDI publication profile
cites work: Q4773298
cites work: Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
cites work: Threshold characterization of graphs with dilworth number two
cites work: Q4165164
cites work: Four classes of perfectly orderable graphs
cites work: Ferrers digraphs and threshold graphs
cites work: Threshold Dimension of Graphs
cites work: Multidimensional scaling and threshold graphs
cites work: Split Graphs Having Dilworth Number Two
cites work: Q4182796
cites work: Q3328583
cites work: Threshold Numbers and Threshold Completions
cites work: Threshold Sequences
cites work: Bithreshold Graphs
cites work: Some properties of 2-threshold graphs
cites work: Hamiltonian threshold graphs
cites work: Sufficient Conditions for Graphs to Have Threshold Number 2
cites work: Extreme degree sequences of simple graphs
cites work: Strict 2-threshold graphs
cites work: Q3686754
cites work: Q3683903
cites work: Incremental modular decomposition
cites work: Q3780408
cites work: Q4134007
cites work: Q3901542
cites work: The polytope of degree sequences
cites work: The Complexity of the Partial Order Dimension Problem
Recommended article: Bithreshold Graphs
Recommended article: Bithreshold graphs
Recommended article: An \(O(n^ 3)\) recognition algorithm for bithreshold graphs
Recommended article: Investigations on the bisection problem
Recommended article: An attractive class of bipartite graphs
description: scientific article; zbMATH DE number 444642