Document Type

Article

Publication Date

2000

Department

Physics & Computer Science

Abstract

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.

Comments

This article was originally published in SIAM Journal on Discrete Mathematics, 13(1): 48-55. © 2000 Society for Industrial and Applied Mathematics

Download

Share

COinS