Approximation Results for the Optimum Cost Chromatic Partition Problem

✍ Scribed by Klaus Jansen

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 246 KB
• Volume: 34
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1022

✦ Synopsis

In this paper, we study the optimum cost chromatic partition OCCP problem for several graph classes. The OCCP problem is the problem of coloring the vertices of a graph such that adjacent vertices get different colors and that the total coloring cost is minimum. We prove several approximation results for the OCCP problem restricted to bipartite, chordal, comparability, interval, permutation, split, and unimodular graphs. We prove that there exists no polynomial approximation Ž< < 0.5y⑀ . algorithm with ratio O V for the OCCP problem restricted to bipartite and interval graphs, unless P s NP. Furthermore, we propose approximation algo-Ž< < 0.5 . rithms with ratio O V for bipartite, interval, and unimodular graphs. Finally, we prove that there exists no polynomial approximation algorithm with ratio Ž< < 1y ⑀ . O V

for the OCCP problem restricted to split, chordal, permutation, and comparability graphs, unless P s NP.