Minimal obstructions to (s,1)-polarity in cographs
share
Let k,l be nonnegative integers. A graph G is (k,l)-polar if its vertex set admits a partition (A,B) such that A induces a complete multipartite graph with at most k parts, and B induces a disjoint union of at most l cliques with no other edges. A graph is a cograph if it does not contain P_4 as an induced subgraph. It is known that (k,l)-polar cographs can be characterized through a finite family of forbidden induced subgraphs, for any fixed choice of k and l. The problem of determining the exact members of such family for k = 2 = l was posted by Ekim, Mahadev and de Werra, and recently solved by Hell, Linhares-Sales and the second author of this paper. So far, complete lists of such forbidden induced subgraphs are known for 0 ≤ k,l ≤ 2; notice that, in particular, (1,1)-polar graphs are precisely split graphs. In this paper, we focus on this problem for (s,1)-polar cographs. As our main result, we provide a recursive complete characterization of the forbidden induced subgraphs for (s,1)-polar cographs, for every non negative integer s. Additionally, we show that cographs having an (s,1)-partition for some integer s (here s is not fixed) can be characterized by forbidding a family of four graphs.
READ FULL TEXT