BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION

Abstract

We describe here a technique of decomposition of bipartite graphs which seems to be as interesting within this context as the well known modular and split techniques for the decomposition of general graphs. In particular, we characterize by forbidden subgraphs the family of bipartite graphs which are totally decomposable (i.e. reducible to single vertices) with respect to our decomposition. This family contains previously known families of graphs such as bicographs and P 6 -free bipartite graphs. As an application we provide polynomial solutions of optimization problems, some of them being NP-complete for general bipartite graphs.