DIMACS TR: 2002-44

Bisplit Graphs

Authors: Andreas Brandstadt, Peter L. Hammer, Van Bang Le, Vadim V. Lozin


A graph is bisplit if it can be partitioned into a stable set and a bi-clique (i.e. a complete bipartite graph). We provide an O(nm) recognition algorithm for these graphs, and characterize them in terms of forbidden induced subgraphs. Moreover, we show that the recognition problem of the slightly larger class of weak bisplit graphs is NP-complete.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-44.ps.gz
DIMACS Home Page