Partitions of graphs into one or two independent sets and cliques: Revised version
Andreas Brandstädt · 1991
lt is shown that it can be recognized in polynomial time whether the vertex set of a finite undirected graph can be partitioned into one or two independent sets and cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized in polynomial time whether a graph can be partitioned into two split graphs. An efficient time bound 0(n2m) is given for the recognition of graphs which can be partitioned into two independent sets and one clique.