Recognizing Perfect 2-Split Graphs
Chı́nh T. Hoàng, Van Bang Lê · SIAM Journal on Discrete Mathematics · 2000
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.