Partitioning cographs into forests and independent sets

To determine the chromatic number of a graph, we seek to partition the vertices into minimum number of independent sets. Similarly, for arboricity, we seek to partition the vertices into minimum number of sets, each of which induces a forest. Both problems seek to partition the vertices into sets that induce a sparse subgraph, and both are NP-hard in general and can be solved in polynomial time on cographs. In this thesis, we consider a mixed problem, where a graph is partitioned into p forests and q independent sets. It is known that for each p and q, the partition problem has a finite complete set of minimal cograph obstructions. For the cases where p = 0 or p = 1, a minimal obstruction characterization of (p, q) partitionability of cographs was previously known. However, it was also known that the number of minimal obstructions grows exponentially with p. We consider the next case of p = 2 and q = 1, and provide a complete list of minimal cograph obstructions. We also provide polynomial time certifying algorithms for the cases p = 1 for any q, and p = 2 and q = 1. We also consider a vertex deletion version of the partition problem. Here, r vertices are allowed to be deleted so that the remaining graph admits a partition into p forests and q independent sets. For this problem, we provide a complete list of minimal cograph obstructions when p = q = r = 1, and p = r = 1, q = 2.