Partitioning cographs into two forests and one independent set (Q779168)

The authors characterize when a cograph has a partition into \(p=2\) forests and \(q=1\) independent set by describing a family of nine minimal obstructions. Namely, a cograph can be partitioned into two forests and one independent set if and only if it does not contain an induced subgraph isomorphic to one of those nine obstructions. In the cases \(p=0\), \(p=1\) and \(q=0\), there were already a list of cograph obstructions known. For \(p=0\), a cograph can be partitioned into \(q\) independent sets if and only if it does not contain \(K_{q+1}\). For \(p=1\), the list of minimal cograph obstructions contains the two graphs \(K_{q+3}\) and \(\overline{q+2K_2}\). In particular, both lists are uniform in the sense that they describe uniformly all forbidden subgraphs for any value of \(q\) and fixed \(p\in \{0,1\}\). The authors investigate whether such a uniform description can be found in the case \(p=2\). Their main result (a list of nine cograph obstructions for \(p=2, q=1\)) implies that this is not the case, as not all of those nine cographs are a generalization of the seven known cograph obstructions for \(p=2, q=0\) given in [\textit{S. G. Hermosillo de la Maza} et al., ``Vertex arboricity of cographs'', Preprint, \url{arXiv:1907.07286}]. The article concludes by sketching how the algorithm given in [loc. cit.] can be modified to certify the non-existence of a partition of a cograph into two forests and one independent set by returning one of the nine minimal obstructions. For the entire collection see [Zbl 1435.68020].