## 5 Parameterization by Number of Vertex Deletions
### Degree and Color-Degree  
By Theorem 6, parameterization by \(\ell\) alone does not yield fixed-parameter tractability. Hence, we consider combinations of \(\ell\) with two parameters. One is the maximum degree \(\Delta\), and the other one is the _maximum color degree_\(\Delta_{C}:=\max_{v\in V}|\{c\mid\exists\{u,v\}\in E:\chi(\{u,v\})=c\}|\), which is the maximum number of colors incident with any vertex in \(G\). This parameter was also considered by [PERSON] [21] for obtaining bounds on the size of minimum rainbow subgraphs. Note that the maximum color degree is upper-bounded by both the maximum degree and by the number of colors in \(G\) and that it may be much smaller than either parameter. First, we show that for the combined parameter \((\Delta,\ell)\) the problem has a polynomial-size problem kernel. To our knowledge, this is the first non-trivial kernelization result for Rainbow Subgraph. As it is common for kernelizations, it is based on a set of polynomial-time executable data reduction rules. The main idea of the kernelization is as follows. We first remove edges whose colors appear very often compared to \(\Delta\) and \(\ell\). Afterwards, deleting any vertex \(v\) \"influences\" only a bounded number of other vertices: at most \(\Delta\) edges are incident with \(v\), and for each of these edges the number of other edges that have the same color depends only on \(\Delta\) and \(\ell\). We then consider some vertices that are in every rainbow cover. To this end, we call a vertex \(v\)_obligatory_ if there is some edge color such that all edges with this color are incident with \(v\). In the data reduction rules, we remove those obligatory vertices that have only obligatory neighbors. Together with the previous reduction rules, we then obtain the kernel by the following argument: If there are many non-obligatory vertices, then we can greedily find a solution, since any vertex deletion has bounded \"influence\". Otherwise, the overall instance size is bounded as every other vertex is a neighbor of some non-obligatory vertex and each non-obligatory vertex has at most \(\Delta\) neighbors. Figure 2: The reduction for showing the W[1]-hardness of Rainbow Subgraph for parameter \(\ell\). The graph of the Independent Set with Perfect Matching instance (shown on the left) has a perfect matching \(\{\{u,v\},\{w,x\}\}\). Accordingly, the four edges from \(v^{*}\) to \(V\) are colored with two colors. The unique colors between the additional vertices which are not from \(V\) are shown in shades of gray. As mentioned above, the first rule removes edges whose color appears very often compared to \(\Delta\) and \(\ell\). Obviously, when we remove edges from the graph, we also remove their entry from \(\chi\). **Rule 1**. : _If there is an edge color \(c\) such that there are more than \(\Delta\ell\) edges with color \(c\), then remove all edges with color \(c\) from \(G\)._  
**Proof of correctness. ** Deleting at most \(\ell\) vertices from \(G\) may destroy at most \(\Delta\ell\) edges. Hence, any subgraph of order \(n-\ell\) of \(G\) contains an edge of color \(c\). Consequently, removing edges of color \(c\) from \(G\) cannot transform a no-instance into a yes-instance. \(\Box\)  
We now deal with obligatory vertices. The first simple rule identifies edge colors that are already covered by obligatory vertices. **Rule 2**. : _If \(G\) contains an edge \(\{u,v\}\) of color \(c\) such that \(u\) and \(v\) are obligatory, then remove all other edges with color \(c\) from \(G\)._  
**Proof of correctness. ** An application of the rule cannot transform a no-instance into a yes-instance, since it removes edges from \(G\) without removing the color from \(G\). Assume that the original instance is a yes-instance. Since \(u\) and \(v\) are obligatory, any rainbow cover contains \(u\) and \(v\). Therefore, any rainbow cover of the original instance contains an edge with color \(c\) and thus it is also a rainbow cover in the new instance, since only edges of color \(c\) are deleted.