ON COCOLOURINGS AND COCHROMATIC NUMBERS OF GRAPHS

A cocolouring of a graph G is a partition of the vertices such that ea ch set of the partition induces either a clique or an independent set in G. The cochromatic number of G is the smallest cardinality of a coc olouring of G. We show that the cochromatic number problem remains NP- complete for line graphs of comparability graphs (and hence for line g raphs and K1.3-free graphs), and we present polynomial time algorithms for computing the cochromatic numbers of chordal graphs and cographs.