On the approximation of Min Split-coloring and Min Cocoloring - Demange, Marc; Ekim, Tinaz; de Werra, Dominique (Journal of Graph Algorithms and Applications, 2006)
We consider two problems, namely Min Split-coloring andMin Cocoloring, that generalize the classical Min Coloring problemby using not only stable sets but also cliques to cover all thevertices of a given graph. We prove the NP-hardness of some cases.We derive approximation results for Min Split-coloring and MinCocoloring in line graphs, comparability graphs and generalgraphs. This provides to our knowledge the first approximationresults for Min Split-coloring since it was defined only veryrecently [,,]. Also, we provide some resultson the approximability of Min Cocoloring and comparisons with MinSplit-coloring and Min Coloring. <!---->