Bisplit graphs

An undirected graph G=(V,E) is a bisplit graph if its vertex set can be partitioned into a stable set and a complete bipartite graph. We provide an O(|V||E|) time recognition algorithm for these graphs and characterize them in terms of forbidden induced subgraphs. We also discuss the problem of recognizing whether G has a stable set S such that the connected components of G[V⧹S] are more than one complete bipartite subgraph.