SOME OPTIMIZATION PROBLEMS ON BIPARTITE STAR123-FREE GRAPHS
|
|
Divide and conquer is a powerful paradigm when dealing with optimization problems. A particular form of this paradigm in graph theory is graph decomposition. For example when applied on particular classes of graphs as cographs, the well known modular decomposition allows efficient solutions for a lot of optimization problems which are NP-complete in the general case as well as for the recognition problem. We consider here a decomposition scheme devoted to bipartite graphs, namely canonical decomposition. Weak bisplit graphs are designed to be completely decomposable with respect to canonical decomposition, that is graphs whose indecomposable subgraphs are reduced to signal vertices. Weak bisplit graphs are also characterized with two forbidden subgraphs, the P7 and Star123 and a linear time recognition algorithm is provide for this class of graphs, in addition some optimization problems for this class are done. Bipartite Star123-free graphs are a natural generalization of weak bisplit graphs, it is proved that the representative indecomposable subgraphs with respect to canonical decomposition for bipartite Star123-free graphs are paths Pk or cycles Ck (k>7) or they bicomplements. In this paper we will extend the results for weak bisplit graphs to bipartite Star123-free graphs, moreover studying clique width problem and matching problem for this class.
|