Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649410 | Discrete Mathematics | 2009 | 8 Pages |
Abstract
Given integers jj and kk and a graph GG, we consider partitions of the vertex set of GG into j+kj+k parts where jj of these parts induce empty graphs and the remaining kk induce cliques. If such a partition exists, we say GG is a (j,k)(j,k)-graph. For a fixed jj and kk we consider the maximum order nn where every graph of order nn is a (j,k)(j,k)-graph. The split-chromatic number of GG is the minimum jj where GG is a (j,j)(j,j)-graph. Further, the cochromatic number is the minimum j+kj+k where GG is a (j,k)(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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tınaz Ekim, John Gimbel,