Minimal obstructions to $(\infty ,k)$-polarity in cographs

Abstract

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,\infty )$-, $(\infty ,k)$-, and $(\infty ,\infty )$-polar graphs can be analogously defined. Ekim, Mahadev and de Werra pioneered in the research on polar cographs, obtaining forbidden induced subgraph characterizations for $(\infty ,\infty )$-polar cographs, as well as for the union of $(\infty ,1)$- and $(1,\infty )$-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 $(\infty ,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 $(\infty ,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,\infty )$-polar cographs.

References in corpus (1)

• Minimal obstructions to $(s,1)$-polarity in cographs