Recognizing perfect 2-split graphs

Authors
Hoang, CT Le, V
Citation
Ct. Hoang et V. Le, Recognizing perfect 2-split graphs, SIAM J DISC, 13(1), 2000, pp. 48-55
Citations number
19
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
08954801 → ACNP
Volume
13
Issue
1
Year of publication
2000
Pages
48 - 55
Database
ISI
SICI code
0895-4801(200001)13:1<48:RP2G>2.0.ZU;2-M
Abstract
A graph is a split graph if its vertices can be partitioned into a clique a nd a stable set. A graph is a k-split graph if its vertices can be partitio ned into k sets, each of which induces a split graph. We show that the stro ng perfect graph conjecture is true for 2-split graphs and we design a poly nomial algorithm to recognize a perfect 2-split graph.