On the approximation of Min Split-coloring and Min Cocoloring

Authors

  • Marc Demange
  • Tinaz Ekim
  • Dominique de Werra

DOI:

https://doi.org/10.7155/jgaa.00129

Keywords:

split-coloring , cocoloring , line graphs , approximation

Abstract

We consider two problems, namely Min Split-coloring and Min Cocoloring, that generalize the classical Min Coloring problem by using not only stable sets but also cliques to cover all the vertices of a given graph. We prove the NP-hardness of some cases. We derive approximation results for Min Split-coloring and Min Cocoloring in line graphs, comparability graphs and general graphs. This provides to our knowledge the first approximation results for Min Split-coloring since it was defined only very recently [,,]. Also, we provide some results on the approximability of Min Cocoloring and comparisons with Min Split-coloring and Min Coloring.

Downloads

Download data is not yet available.

Downloads

Published

2024-03-16

How to Cite

Demange, M., Ekim, T., & de Werra, D. (2024). On the approximation of Min Split-coloring and Min Cocoloring. Journal of Graph Algorithms and Applications, 10(2), 297–315. https://doi.org/10.7155/jgaa.00129

Issue

Section

Articles

Categories