# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Packing Problems
#### 4.1.2 Vertex Coloring  
A problem related to Independent Set is the Vertex Coloring problem, for which the vertices need to be colored with integer values, such that no two adjacent vertices have the same color (which means that each color class forms an independent set in the graph). The task is to minimize the number of used colors. For planar graphs the problem has a polynomial time \(4/3\)-approximation algorithm (Bansal et al., 2017) via the celebrated Four Color Theorem, and a better approximation is not possible in polynomial time [101]. Using this algorithm, a \(7/3\)-approximation can be computed in FPT time when parameterizing by the size of a planar deletion set [8]. When generalizing planar graphs by excluding any fixed minor, and taking its size as the parameter, a \(2\)-approximation can be computed in FPT time [102]. Due to the NP-hardness for planar graphs [101], neither of these two parameterizations admits a PAS, unless P = NP. **Theorem 12** ([8, 102]). : _For the Vertex Coloring problem_  
* _[leftmargin=*]_
* \(a\) \(7/3\)_-approximation can be computed in_ \(k^{k}n^{O(1)}\) _time, where_ \(k\) _is the size of a minimum planar deletion set, and_
* \(a\) \(2\)_-approximation can be computed in_ \(f(k)n^{O(1)}\) _time for some function_ \(f\)_, where_ \(k\) _is the size of an excluded minor of the input graph._  
One way to generalize Vertex Coloring is to see each color class as an induced graph of degree \(0\). The Defective Coloring problem [103] correspondingly asks for a coloring of the vertices, such that each color class induces a graph of maximum degree \(\Delta\), for some given \(\Delta\). The aim again is to minimize the number of used colors. In contrast to Vertex Coloring, the Defective Coloring problem is W[1]-hard [104] parameterized by the treewidth. This parameter measures how \"tree-like\" a graph is, and is defined as follows. **Definition 1**. : _A tree decomposition of a graph \(G=(V,E)\) is a tree \(T\) for which every node is associated with a bag \(X\subseteq V\), such that the following properties hold:_  
1. _[leftmargin=*]_
2. _the union of all bags is the vertex set_ \(V\) _of_ \(G\)_,_
3. _for every edge_ \((u,v)\) _of_ \(G\)_, there is a node of_ \(T\) _for which the associated bag contains_ \(u\) _and_ \(v\)_, and_
4. _for every vertex_ \(u\) _of_ \(G\)_, all nodes of_ \(T\) _for which the associated bags contain_ \(u\)_, induce a connected subtree of_ \(T\)_._  
_The width of a tree decomposition is the size of the largest bag minus \(1\) (which implies that a tree has a decomposition of width \(1\) where each bag contains the endpoints of one edge). The treewidth of a graph is the smallest width of any of its tree decompositions._  
Treewidth is fundamental parameter of a graph and will be discussed more elaborately in Section 4.6.1. However, it is worth mentioning here that Vertex Coloring is in FPT when parameterized by treewidth. The strong polynomial-time approximation lower bound of \(n^{1-\varepsilon}\) for Vertex Coloring[81] naturally carries over to the more general Defective Coloring problem. A much improved approximation factor of \(2\) is possible though in FPT time if the parameter is the treewidth [104]. It can be shown however, that a PAS is not possible in this case, as there is no \((3/2-\varepsilon)\)-approximation algorithm for any \(\varepsilon>0\) parameterized by the treewidth [104], unless FPT = W[1]. A natural question is whether the bound \(\Delta\) of Defective Coloring can be approximated instead of the number of colors. For this setting, a bicriteria PAS parameterized by the treewidth exists [104], which computes a solution with the optimum number of colors where each color class induces a graph of maximum degree at most \((1+\varepsilon)\Delta\). **Theorem 13** ([104]).