Ekim, TinazGimbel, John2010-11-302010-11-302010-11-30200910.1016/j.disc.2008.06.027https://infoscience.epfl.ch/handle/20.500.14299/59696WOS:000271375700007Given 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.(j, k)-coloringSplit graphCocoloringIndependent SetsCliquestext::journal::journal article::research article