## Remarks on split graphs and related notions

- Date: 12/05/2006

John Gimbel (University of Alaska, Fairbanks)

University of British Columbia

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.

Discrete Math Seminar 2006