On the minimum and maximum selective graph coloring problems in some graph classes
Discrete Applied Mathematics, cilt.204, ss.77-89, 2016 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 204
- Basım Tarihi: 2016
- Doi Numarası: 10.1016/j.dam.2015.10.005
- Dergi Adı: Discrete Applied Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.77-89
- Anahtar Kelimeler: Approximation, Complexity, Graph classes
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Given a graph together with a partition of its vertex set, the minimum selective coloring problem consists of selecting one vertex per partition set such that the chromatic number of the subgraph induced by the selected vertices is minimum. The contribution of this paper is twofold. First, we investigate the complexity status of the minimum selective coloring problem in some specific graph classes motivated by some models described in Demange et al. (2015). Second, we introduce a new problem that corresponds to the worst situation in the minimum selective coloring; the maximum selective coloring problem aims to select one vertex per partition set such that the chromatic number of the subgraph induced by the selected vertices is maximum. We motivate this problem by different models and give some first results concerning its complexity.