Approximating minimum cocolorings. (Q1853153)

A cocoloring of a graph \(G\) is a partition of the vertex set of \(G\) such that each set of the partition is either a clique or an independent set in \(G.\) Some special cases of the minimum cocoloring problem are of particular interest. We provide polynomial-time algorithms to approximate a minimum cocoloring on graphs, partially ordered sets and sequences. In particular, we obtain an efficient algorithm to approximate within a factor of \(1.71\) a minimum partition of a partially ordered set into chains and antichains, and a minimum partition of a sequence into increasing and decreasing subsequences.