(p, k)-coloring problems in line graphs
Theoretical Computer Science, cilt.349, sa.3, ss.462-474, 2005 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 349 Sayı: 3
- Basım Tarihi: 2005
- Doi Numarası: 10.1016/j.tcs.2005.09.037
- Dergi Adı: Theoretical Computer Science
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.462-474
- Anahtar Kelimeler: Cocoloring, Line graphs, Split-coloring
- Boğaziçi Üniversitesi Adresli: Hayır
Özet
The (p,k)-coloring problems generalize the usual coloring problem by replacing stable sets by cliques and stable sets. Complexities of some variations of (p,k)-coloring problems (split-coloring and cocoloring) are studied in line graphs; polynomial algorithms or proofs of NP-completeness are given according to the complexity status. We show that the most general (p,k)-coloring problems are more difficult than the cocoloring and the split-coloring problems while there is no such relation between the last two problems. We also give complexity results for the problem of finding a maximum (p,k)-colorable subgraph in line graphs. Finally, upper bounds on the optimal values are derived in general graphs by sequential algorithms based on Welsh-Powell and Matula orderings. © 2005 Elsevier B.V. All rights reserved.