Partitioning graphs into complete and empty graphs
Discrete Mathematics, cilt.309, sa.19, ss.5849-5856, 2009 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 309 Sayı: 19
- Basım Tarihi: 2009
- Doi Numarası: 10.1016/j.disc.2008.06.027
- Dergi Adı: Discrete Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.5849-5856
- Anahtar Kelimeler: (j, k)-coloring, Cocoloring, Split graph
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Given 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. © 2009.