BI-COMPLEMENT REDUCIBLE GRAPHS

We introduce a new family of bipartite graphs which is the bipartite a nalogue of the class of complement reducible graphs or cographs. A bi- complement reducible graph or bi-cograph is a bipartite graph G = (W b oolean OR B, E) that can be reduced to single vertices by recursively hi-complementing the edge set of all connected bipartite subgraphs. Th e bi-complemented graph <(G)over bar (bip)> Of G is the graph having t he same vertex set W boolean OR B as G, while its edge set is equal to IV x B - E. The aim of this paper is to show that there exists an equ ivalent definition of bi-cographs by three forbidden configurations. W e also propose a tree representation for this class Of graphs. (C) 199 7 Academic Press.