Bipartite (P_6,C_6 )-Free Graphs, Recognition and Optimization Problems

The canonical decomposition of a bipartite graph is a new decompositionmethod that involves three operators, parallel, series and K+S. The class of weak bisblit graphs is totally decomposable with respect of these operators, and the class of bicographs is totally decomposable with respect of parallel and series operators. We prove in this paper that the class of bipartite (P_6,C_6)-free graphs is exactly the class of bipartite graphs that are totally decomposable with respect of parallel and K+S operators. We simplify the recognition algorithm of weak-bisplit graphs to adepte with bipartite (P_6,C_6)-free graphs. As a result of this adapted algorithm, we prsent efficient solutions in this class of graphs for two optimization graph problems, the first is the maximm balanced bi-clique problem and the the second is the maximum independent set problem.