Minimal obstructions to (∞, k)-polarity in cographs
share
A graph is a cograph if it does not contain a 4-vertex path as an induced subgraph. An (s, k)-polar partition of a graph G is a partition (A, B) of its vertex set such that A induces a complete multipartite graph with at most s parts, and B induces the disjoint union of at most k cliques with no other edges. A graph G is said to be (s, k)-polar if it admits an (s, k)-polar partition. The concepts of (s, ∞)-, (∞, k)-, and (∞, ∞)-polar graphs can be analogously defined. Ekim, Mahadev and de Werra pioneered in the research on polar cographs, obtaining forbidden induced subgraph characterizations for (∞, ∞)-polar cographs, as well as for the union of (∞, 1)- and (1, ∞)-polar cographs. Recently, a recursive procedure for generating the list of cograph minimal (s,1)-polar obstructions for any fixed integer s was found, as well as the complete list of (∞, 1)-polar obstructions. In addition to these results, complete lists of minimal (s, k)-polar cograph obstructions are known only for the pair (2, 2). In this work we are concerned with the problem of characterizing (∞, k)-polar cographs for a fixed k through a finite family of forbidden induced subgraphs. As our main result, we provide complete lists of forbidden induced subgraphs for the cases k=2 and k=3. Additionally, we provide a partial recursive construction for the general case. By considering graph complements, these results extend to (s, ∞)-polar cographs.
READ FULL TEXT