Partitions of generalized split graphs
Oren Shklarsky · Summit (Simon Fraser University) · 2012
We discuss matrix partition problems for graphs that admit a partition into k independent sets and ` cliques. We show that when k + ` 6 2, any matrix M has finitely many (k; `) minimal obstructions and hence all of these problems are polynomial time solvable. We provide upper bounds for the size of any (k; `) minimal obstruction when k = ` = 1 (split graphs), when k = 2; ` = 0 (bipartite graphs), and when k = 0; ` = 2 (co-bipartite graphs). When k = ` = 1, we construct an exponential size split minimal obstruction for a particular matrix M, obtaining the first known exponential lower bound for any minimal obstruction. The construction also shows that the upper bounds are “nearly” tight.