Physics & Computer Science
A graph is a split graph if its vertices can be partitioned into a clique and a stable set. A graph is a k-split graph if its vertices can be partitioned into k sets, each of which induces a split graph. We show that the strong perfect graph conjecture is true for 2-split graphs and we design a polynomial algorithm to recognize a perfect 2-split graph.
Hoàng, Chính T. and Le, Van Bang, "Recognizing Perfect 2-Split Graphs" (2000). Physics and Computer Science Faculty Publications. 73.