ALCOMFT-TR-01-180

Fedor V. Fomin, Dieter Kratsch and Jean-Christophe Novelli
Approximating minimum cocolourings
Paderborn. Work package 4. October 2001.

Abstract: A cocolouring 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 cocolouring problem are of particular interest.

We provide polynomial-time algorithms to approximate a minimum cocolouring 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.

Postscript file: ALCOMFT-TR-01-180.ps.gz (94 kb).