Three-quarter approximation for the number of unused colors in graph coloring
Since it is hard to approximate \(\chi(G)\), the minimum number of colors in a graph coloring, the authors consider to approximate the maximum number of unused colors. This approximation is to maximize the ratio \(r_A=(n-A(G))/(n-\chi(G))\), where \(A(G)\) is the number of colors found by a polynomial-time coloring \(A\) when used to graph \(G\). The authors propose a new polynomial algorithm with \(r_A=3/4\), which improves the previous result of 2/3. The key part of the algorithm is to approximate \(n-\phi(G)\) with ratio 3/4 for 4-clique-free graphs, where \(\phi(G)\) is the minimum number of cliques to which the vertices of \(G\) can be partitioned. The algorithm uses a concept similar to the notion of augmenting path in the classical matching problem, however, more complicated.
- Approximation results for the minimum graph coloring problem
- Covering edges by cliques with regard to keyword conflicts and intersection graphs
- scientific article; zbMATH DE number 3906496 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improving the performance guarantee for approximate graph coloring
- Maximizing the number of unused colors in the vertex coloring problem
- On the hardness of approximating minimization problems
- Some simplified NP-complete graph problems
- The general maximum matching algorithm of Micali and Vazirani
This page was built for publication: Three-quarter approximation for the number of unused colors in graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1818979)
