Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j + k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j, k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j, k)-graph. The split-chromatic number of G is the minimum j where G is a (j, j)-graph. Further, the cochromatic number is the minimum j + k where G is a (j, k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs. (C) 2009 Published by Elsevier B.V.