Recognizing the P4-structure of bipartite graphs

AbstractThe P4-structure of a graph G=(V,E) is a hypergraph H=(V,E) such that the hyperedges from H correspond to the vertex sets of the induced P4s in G. The Semi Strong Perfect Graph Theorem states that a graph is perfect if and only if it has the P4-structure of a perfect graph. While at present no polynomial-time algorithm is known to recognize the P4-structure of perfect graphs, first results have been obtained for special subclasses of perfect graphs. In this note we present an algorithm which decides efficiently whether a given hypergraph represents the P4-structure of a bipartite graph