Remarks on split graphs and related notions

  • Date: 12/05/2006
Lecturer(s):

John Gimbel (University of Alaska, Fairbanks)

Location: 

University of British Columbia

Topic: 

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.

Other Information: 

Discrete Math Seminar 2006

Sponsor: 

pims