\[lem:mfis\_with\_order5\]). It is not difficult to see that bull is a bithreshold graph just by checking the definition in [@HammerMP93].

Note that the concept of double-threshold digraphs introduced by Hamburger et al. [@HamburgerMPSX18] is concerned with directed acyclic graphs defined from a generalization of semiorders involving two thresholds and not related to threshold graphs or double-threshold graphs.

#### Pairwise compatibility graphs. {#pairwise-compatibility-graphs. .unnumbered}

Motivated by uniform sampling from phylogenetic trees in bioinformatics, Kearney, Munro, and Phillips [@KearneyMP03] defined pairwise compatibility graphs. A graph $G=(V,E)$ is a *pairwise compatibility graph* if there exists a quadruple ($T$, ${\mathtt{w}}$, ${\mathtt{lb}}$, ${\mathtt{ub}}$), where $T$ is a tree, ${\mathtt{w}}\colon E(T) \to {\mathbb{R}}$, and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$, such that the set of leaves in $T$ coincides with $V$ and $uv \in E$ if and only if the (weighted) distance $d_{T}(u, v)$ between $u$ and $v$ in $T$ satisfies ${\mathtt{lb}}\le d_{T}(u,v) \le {\mathtt{ub}}$.

Since its introduction, several authors have studied properties of pairwise compatibility graphs, but the existence of a polynomial-time recognition algorithm for that graph class has been open. The survey article by Calamoneri and Sinaimeri [@CalamoneriS16] proposed to look at the class of pairwise compatibility graphs defined on stars (i.e., star pairwise compatibility graphs), and 