Recognizing the P-4-structure of bipartite graphs

The P-4-structure of a graph G=(V, E) is a hypergraph H=(V, E) such that th e hyperedges from H correspond to the vertex sets of the induced P(4)s in G . The Semi Strong Perfect Graph Theorem states that a graph is perfect if a nd only if it has the P-4-structure of a perfect graph. While at present no polynomial-time algorithm is known to recognize the P-4-structure of perfe ct graphs, first results have been obtained for special subclasses of perfe ct graphs. Ln this note we present an algorithm which decides efficiently w hether a given hypergraph represents the P-4-structure of a bipartite graph . (C) 1999 Elsevier Science B.V. All rights reserved.