Remarks on split graphs and related notions

A graph is split if its vertices can be covered by two sets A and B where A induces a complete graph and B induces an empty graph. This concept has many related notions. For example, the number of non-isomorphic set covers of a set of order n is the number of non-isomorphic split graphs of order n. We consider split graphs and three extensions: cochromatic number, split chromatic number and (j,k)-colorings. The cochromatic number of a graph is the minimum number of colors necessary to color the vertices so that each color class induces a complete or empty graph. The split chromatic number is the minimum number of colors used to color the vertices so that each color class induces a split graph. We focus our attention on (j,k)-colorings. A (j,k)-coloring of a graph is a covering of the vertex set using j+k parts where j parts induce complete graphs and k parts induce empty graphs. We consider a simple extremal problem: given j and k, what is the largest n so that every n-graph has a (j,k)-coloring. We also consider some results on computational complexity.