- 作者：Marc Demange ; Tı ; naz Ekim and Dominique de Werra
- 关键词：Cocoloring ; Split-coloring ; Line graphs
- 刊名：Theoretical Computer Science
- 出版年：2005
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：16 December 2005
- 卷：349
- 期：3
- 页码：462-474
- 文件大小：246 K
摘要
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.