  Min-Max orderings correspond to conservative lattice polymorphisms. Digraphs
with Min-Max orderings have polynomial time solvable minimum cost homomorphism
problems. They can also be viewed as digraph analogues of proper interval
graphs and bigraphs.
  We give a forbidden structure characterization of digraphs with a Min-Max
ordering which implies a polynomial time recognition algorithm. We also
similarly characterize digraphs with an extended Min-Max ordering, and we apply
this characterization to prove a conjectured form of dichotomy for minimum cost
homomorphism problems.
