Three-quarter approximation for the number of unused colors in graph coloring (Q1818979)

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.