DIMACS TR: 2002-44
Bisplit Graphs
Authors: Andreas Brandstadt, Peter L. Hammer, Van Bang Le, Vadim V. Lozin
ABSTRACT
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