graphs that gives a simple linear-time recognition algorithm. We first show that every double-threshold graph is a permutation graph (but not vice versa) and that a bipartite graph is a double-threshold graph if and only if it is a permutation graph. These facts imply that many NP-hard graph problems are polynomial-time solvable on (bipartite or non-bipartite) double-threshold graphs. We then show that a graph is a double-threshold graph if and only if an auxiliary graph constructed from the original graph is a bipartite permutation graph. This characterization gives a linear-time algorithm for recognizing double-threshold graphs.

Recently, we have realized that Jamison and Sprague [@JamisonS19] have independently showed that all double-threshold graphs are permutation graphs and that all bipartite permutation graphs are double-threshold graphs. Their proofs are based on a vertex-ordering characterization of permutation graphs and a BFS structure of bipartite permutation graphs, while ours are direct transformations between vertex weights and permutation diagrams. Note that in their paper Jamison and Sprague [@JamisonS19] used the term *bi-threshold graphs* instead of double-threshold graphs. However, the name of “bi-threshold graphs” is already used[^1] by Hammer and Mahadev [@HammerM85] for a different generalization of threshold graphs (see below). Thus, even though “bi-threshold” would sound 