Abstract of Paper |

*On a Generalization of Bi-complement Reducible Graphs*

by Vadim V. Lozin

**Abstract:**

A graph is called complement reducible (a cograph for short) if every its induced subgraph with at least two vertices is either disconnected or the complement to a disconnected graph. The bipartite analog of cographs, bi-complement reducible graphs, has been characterized recently by three forbidden induced subgraphs: $Star_{1,2,3}$, $Sun_4$ and $P_7$, where $Star_{1,2,3}$ is the graph with vertices $a,b,c,d,e,f,g$ and edges $(a,b)$, $(b,c)$, $(c,d)$, $(d,e)$, $(e,f)$, $(d,g)$, and $Sun_4$ is the graph with vertices $a,b,c,d,e,f,g,h$ and edges $(a,b)$, $(b,c)$, $(c,d)$, $(d,a)$, $(a,e)$, $(b,f)$, $(c,g)$, $(d,h)$. In the present paper, we propose a structural characterization for the class of bipartite graphs containing no graphs $Star_{1,2,3}$ and $Sun_4$ as induced subgraphs. Based on the proposed characterization we prove that the clique-width of these graphs is at most five that leads to polynomial algorithms for a number of problems which are NP-complete in general bipartite graphs.