New characterizations of proper interval bigraphs (Q896097)

An interval bigraph is a bipartite graph that can be obtained by assigning an interval to each vertex in such a way that vertices that do not belong to the same partite set are adjacent if and only if the corresponding intervals intersect. Such a graph is called proper if the intervals can also be chosen in such a way that none of them is completely contained in another. This paper provides three new characterisations of proper interval bigraphs: as bipartite graphs avoiding so-called ``astral'' triples of edges, in terms of the concept of dominating pairs, and by means of the biadjacency matrix.