Bipartite bithreshold graphs
From MaRDI portal
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.
Recommendations
Cites work
- Bithreshold Graphs
- Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
- Extreme degree sequences of simple graphs
- Ferrers digraphs and threshold graphs
- Four classes of perfectly orderable graphs
- Hamiltonian threshold graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 3908482 (Why is no real title available?)
- scientific article; zbMATH DE number 4043213 (Why is no real title available?)
- scientific article; zbMATH DE number 3710208 (Why is no real title available?)
- scientific article; zbMATH DE number 3561379 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3618209 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- Incremental modular decomposition
- Multidimensional scaling and threshold graphs
- Some properties of 2-threshold graphs
- Split Graphs Having Dilworth Number Two
- Strict 2-threshold graphs
- Sufficient Conditions for Graphs to Have Threshold Number 2
- The Complexity of the Partial Order Dimension Problem
- The polytope of degree sequences
- Threshold characterization of graphs with dilworth number two
- Threshold Dimension of Graphs
- Threshold Numbers and Threshold Completions
- Threshold Sequences
Cited in
(29)- Bipartable graphs
- Bipartite permutation graphs
- Strict 2-threshold graphs
- Bipartite dimensions and bipartite degrees of graphs
- Bi-complement reducible graphs
- Nearly bipartite graphs
- Bipartite-perfect graphs
- Double-threshold permutation graphs
- Bisimplicial edges in bipartite graphs
- Bipartite finite Toeplitz graphs
- Bithreshold graphs
- Bipartite-perfect graphs
- Investigations on the bisection problem
- Algorithm for identifying (2,2)-bipartite graphs
- scientific article; zbMATH DE number 5348111 (Why is no real title available?)
- scientific article; zbMATH DE number 5545497 (Why is no real title available?)
- Bithreshold Graphs
- scientific article; zbMATH DE number 4010572 (Why is no real title available?)
- Some properties of 2-threshold graphs
- An attractive class of bipartite graphs
- On bipartite‐mixed graphs
- scientific article; zbMATH DE number 3997845 (Why is no real title available?)
- scientific article; zbMATH DE number 4193736 (Why is no real title available?)
- On bipartite powers of bigraphs
- scientific article; zbMATH DE number 6469239 (Why is no real title available?)
- scientific article; zbMATH DE number 7324127 (Why is no real title available?)
- Difference graphs
- An \(O(n^ 3)\) recognition algorithm for bithreshold graphs
- Bipolarizable graphs
This page was built for publication: Bipartite bithreshold graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688258)
