V$ and $y \in Y$, we have ${\mathtt{w}}(v) + {\mathtt{w}}(y) = {\mathtt{w}}_{G}(v) + {\mathtt{w}}_{H}(y) - \alpha < {\mathtt{lb}}$.

By Lemmas \[lem:at-most-one-nonbipartite\] and \[lem:disjoint-bicomponent\], we have the following corollary.

\[cor:component\] A graph is a double-threshold graph if and only if it contains at most one non-bipartite component and all components are double-threshold graphs.

Permutation graphs
------------------

A graph $G=(V,E)$ is a *permutation graph* if there exist linear orderings $\prec_1, \prec_2$ on $V$ with the following property: $$uv \in E \iff (u \prec_1 v \text{ and } v \prec_2 u) \text{ or } (u \prec_2 v \text{ and } v \prec_1 u).$$ We say that $\prec_{1}$ and $\prec_{2}$ *define* the permutation graph $G$. We call $\prec_{1}$ a *permutation ordering* of $G$ if there exists a linear ordering $\prec_{2}$ satisfying the condition above. Since $\prec_{1}$ and $\prec_{2}$ play a symmetric role in the definition, $\prec_{2}$ is also a permutation ordering of $G$. Note that for a graph $G$ and a permutation ordering $\prec_{1}$ of $G$, the other ordering $\prec_{2}$ that defines $G$ together with $\prec_{1}$ is uniquely determined. Also note that if $\prec_{1}$ and $\prec_{2}$ define $G$, then $\prec_{1}^{\mathrm{R}}$ and $\prec_{2}^{\mathrm{R}}$ also define $G$, where $\prec^{\mathrm{R}}$ denotes the reversed ordering of $\prec$.

We 