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.