Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00129
On the approximation of Min Split-coloring and Min Cocoloring
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.
|
Journal Supporters
|