# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Packing Problems
#### 4.1.2 Vertex Coloring
: _For the Defective Coloring problem, given a tree decomposition of width \(k\) of the input graph,_  
* _[leftmargin=*]_
* _a solution with the optimum number of colors where each color class induces a graph of maximum degree_ \((1+\varepsilon)\Delta\) _can be computed in_ \((k/\varepsilon)^{O(k)}n^{O(1)}\) _time for any_ \(\varepsilon>0\)_,_
* \(a\) \(2\)_-approximation (of the optimum number of colors) can be computed in_ \(k^{O(k)}n^{O(1)}\) _time, but_
* _no_ \((3/2-\varepsilon)\)_-approximation (of the optimum number of colors) can be computed in_ \(f(k)n^{O(1)}\) _time for any_ \(\varepsilon>0\) _and computable function_ \(f\)_, unless FPT = W[1]._The algorithms of the previous theorem build on the techniques of [105] using approximate addition trees in combination with dynamic programs that yield XP algorithms for these problems. This technique can be applied to various problems (cf. Section 4.2), including a different generalization of Vertex Coloring called Equitable Coloring. Here the aim is to color the vertices of a graph with as few colors as possible, such that every two adjacent vertices receive different colors, and all color classes contain the same number of vertices. It is a generalization of Vertex Coloring, since one may add a sufficiently large independent set (i.e., a set of isolated vertices) to a graph such that the number of colors needed for an optimum Vertex Coloring solution is the same as for an optimum Equitable Coloring solution. The Equitable Coloring problem is W[1]-hard even when combining the number of colors needed and the treewidth of the graph as parameters [106]. On the other hand, a PAS exists [105] if the parameter is the cliquewidth of the input graph. This is a weaker parameter than treewidth, as the cliquewidth of a graph is bounded as a function of its treewidth. However, while bounded treewidth graphs are sparse, cliquewidth also allows for dense graphs (such as complete graphs). Formally, a graph of cliquewidth \(\ell\) can be constructed using the following recursive operations using \(\ell\) labels on the vertices:  
1. Introduce(\(x\)): create a graph containing a singleton vertex labelled \(x\in\{1,\ldots,\ell\}\). 2. Union(\(G_{1},G_{2}\)): return the disjoint union of two vertex-labelled graphs \(G_{1}\) and \(G_{2}\). 3. Join(\(G,x,y\)): add all edges connecting a vertex of label \(x\) with a vertex of label \(y\) to the vertex-labelled graph \(G\). 4. Rename(\(G,x,y\)): change the label of every vertex of \(G\) with label \(x\) to \(y\in\{1,\ldots,\ell\}\). A cliquewidth expression with \(\ell\) labels is a recursion tree describing how to construct a graph using the above four operations using only labels from the set \(\{1,\ldots,\ell\}\). Notice that the cliquewidth of a complete graph is two and therefore we have graphs of bounded clique-width but unbounded treewidth. As stated earlier the cliquewidth of a graph is bounded above exponentially in its treewidth and this dependence is tight for some graph families [107]. The PAS for Equitable Coloring will compute a coloring using at most \(k\) colors such that the ratio between the sizes of any two color classes is at most \(1+\varepsilon\). In this sense it is a bicriteria approximation algorithm. Theorem 14 ([105]): _For the Equitable Coloring problem, given a cliquewidth expression with \(\ell\) labels for the input graph, a solution with optimum number of colors where the ratio between the sizes of any two color classes is at most \(1+\varepsilon\), can be computed in \((k/\varepsilon)^{\mathcal{O}(\ell\ell)}n^{\mathcal{O}(1)}\) time [108, 109] for any \(\varepsilon>0\), where \(k\) is the optimum number of colors._  
A variant of Vertex Coloring is the Min Sum Coloring problem, where, instead of minimizing the number of colors, the aim is to minimize the sum of (integer) colors, where the sum is taken over all vertices.