Partitioning cographs into cliques and stable sets
Discrete Optimization, cilt.2, sa.2, ss.145-153, 2005 (Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 2 Sayı: 2
- Basım Tarihi: 2005
- Doi Numarası: 10.1016/j.disopt.2005.03.003
- Dergi Adı: Discrete Optimization
- Derginin Tarandığı İndeksler: Scopus
- Sayfa Sayıları: ss.145-153
- Anahtar Kelimeler: (p,k)-coloring, Cocoloring, Cographs, Split-coloring
- Boğaziçi Üniversitesi Adresli: Hayır
Özet
We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs [Feder et al., SIAM J. Discrete Math. 16 (3) (2003) 449-478], chordal graphs [Hell et al., Discrete Appl. Math. 141 (2004) 185-194] and cacti for the case where k=p in [Ekim and de Werra, On split-coloring problems, submitted for publication] where some upper and lower bounds on the optimal value minimizing k are also presented. We focus on cographs and devise some efficient algorithms for solving (p,k)-coloring problems and cocoloring problems in O(n2+nm) time and O(n3/2) time, respectively. We also give an algorithm for finding the maximum induced (p,k)-colorable subgraph. In addition to this, we present characterizations of (2,1)- and (2,2)-colorable cographs by forbidden configurations. © 2005 Elsevier B.V. All rights reserved.