On split-coloring problems
Journal of Combinatorial Optimization, cilt.10, sa.3, ss.211-225, 2005 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 10 Sayı: 3
- Basım Tarihi: 2005
- Doi Numarası: 10.1007/s10878-005-4103-7
- Dergi Adı: Journal of Combinatorial Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.211-225
- Anahtar Kelimeler: Packing, Partitioning, Split-coloring, Vertex covering by split graphs
- Boğaziçi Üniversitesi Adresli: Hayır
Özet
We study a new coloring concept which generalizes the classical vertex coloring problem in a graph by extending the notion of stable sets to split graphs. First of all, we propose the packing problem of finding the split graph of maximum size where a split graph is a graph G = (V,E) in which the vertex set V can be partitioned into a clique K and a stable set S. No condition is imposed on the edges linking vertices in S to the vertices in K. This maximum split graph problem gives rise to an associated partitioning problem that we call the split-coloring problem. Given a graph, the objective is to cover all his vertices by a least number of split graphs. Definitions related to this new problem are introduced. We mention some polynomially solvable cases and describe open questions on this area. © 2005 Springer Science + Business Media, Inc.