## 5 Parameterization by Number of Vertex Deletions
### Degree and Color-Degree
Then, the graph \(G^{\prime}[S]\) is clearly also a rainbow cover as it contains all edge colors that are in both \(G\) and \(G^{\prime}\) plus possibly the new edge color \(\chi(\{v,w\})\). Now assume that the rule removes \(x\). In this case, \(G^{\prime}[S^{\prime}]\) with \(S^{\prime}:=S\setminus\{x\}\) is a rainbow cover by the same arguments. Since \(|V|-|V^{\prime}|=|S|-|S^{\prime}|\), the claim holds also in this case. \"\(\Leftarrow\)\": Let \(S^{\prime}\) be a set such that \(G^{\prime}[S^{\prime}]\) is a rainbow cover. If the rule does not remove \(x\) from \(G\), then \(\{u,v,w,x\}\subseteq S\) as these four vertices are obligatory in \(G^{\prime}\) (\(\{u,v\}\) and \(\{v,w\}\) have unique colors and \(x\) has in \(G^{\prime}\) an obligatory neighbor, so the edge between them is obligatory). Therefore, \(G[S^{\prime}]\) is also a rainbow cover by similar arguments as above. Now assume that the rule removes \(x\) from \(G\). In this case \(\{u,v,w\}\subseteq S^{\prime}\) as all three vertices are obligatory in \(G^{\prime}\). Then, \(G[S]\) with \(S:=S^{\prime}\cup\{x\}\) is a rainbow cover of \(G\). First, the only color contained in \(G\) not in \(G^{\prime}\) is \(\chi(\{w,x\})\), and this color is contained in \(G[S]\). Second, the only edge present in \(G^{\prime}[S^{\prime}]\) not in \(G[S]\) is possibly \(\{v,w\}\). If \(\{v,w\}\) is not in \(G[S]\), then there is also no other edge of color \(\chi(\  
**Proof. ** We consider a special type of vertex set that can be safely deleted. To this end, call a vertex set \(S\) a _colorful packing_ if  
1. no vertex in \(S\) is obligatory, and
2. for all \(u,v\in S\) the set of colors incident with \(u\) is disjoint from the set of colors incident with \(v\). Assume that \((G,\chi)\) has a _colorful packing_ of size \(\ell\). Then, \(G-S\) is a rainbow cover of order \(k\): For each color incident with some vertex \(v\) in \(S\), there are two other vertices in \(V\) that are connected by an edge with this color (as \(v\) is not obligatory). By the second condition, these two vertices are not in \(S\). Hence, this edge color is contained in \(G-S\). Summarizing, if \((G,\chi)\) contains a colorful packing of size at least \(\ell\), then \((G,\chi)\) is a yes-instance. Now, assume that a maximum-cardinality colorful packing \(S\) in \(G\) has size less than \(\ell\). Each vertex in \(S\) is incident with at most \(\Delta_{C}\) colors. For each of these colors, the graph induced by the edges of this color has at most \(\Delta\ell\) edges and thus at most \(2\Delta\ell\) vertices, since the instance is reduced with respect to Rule 1. Let \(T\) denote the set of vertices in \(V\setminus S\) that are incident with at least one edge that has the same color as as an edge incident with some vertex in \(S\). By the above discussion,  
\[|T|\leq 2\Delta\cdot\Delta_{C}\cdot\ell\cdot(\ell-1). \tag{14}\]  
Note that \(T\) includes all neighbors of vertices in \(S\). By the maximality of \(S\), all vertices in \(V\setminus(S\cup T)\) are obligatory. Now partition \(V\setminus(S\cup T)\) into the set \(X\) that has neighbors in \(T\) and the set \(Y\) that has only neighbors in \((X\cup Y)\). The set \(X\) has size at most \((2\Delta_{C}\cdot\Delta\cdot\ell\cdot(\ell-1))\cdot\Delta\) since the maximum degree in \(G\) is \(\Delta\). The set \(Y\) has size at most \(1\) since otherwise one of the Rules 3 to 5 applies: Every vertex in \(Y\) is obligatory and has only obligatory neighbors. If two vertices of \(Y\) have a common neighbor, then Rule 4 applies. If \(G\) has a connected component consisting only of vertices of \(Y\), then Rule 3 applies. The only remaining case is that \(Y\) has two vertices \(u\) and \(x\) that have different obligatory neighbors in \(X\). In this case, Rule 5 applies. Since \(S\) has size at most \(\ell-1\), \(G\) contains thus at most  
\[\ell-1+2\Delta\cdot\Delta_{C}\cdot\ell\cdot(\ell-1)+2\Delta^{2}\cdot\Delta_{ C}\cdot\ell\cdot(\ell-1)+1<2\Delta\cdot(\Delta+1)\cdot\Delta_{C}\cdot\ell^{2}\]  
vertices.