Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00129 On the approximation of Min Split-coloring and Min Cocoloring Marc Demange , Tinaz Ekim , and Dominique de Werra Vol. 10, no. 2, pp. 297-315, 2006. Regular paper 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.
|
Submitted: June 2005. Revised: April 2006. Communicated by Martin Fürer |
Journal of Graph Algorithms and Applications |