{"ID":2893842,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12005","arxiv_id":"2507.12005","title":"Kernelization for list $H$-coloring for graphs with small vertex cover","abstract":"For a fixed graph $H$, in the List $H$-Coloring problem, we are given a graph $G$ along with list $L(v) \\subseteq V(H)$ for every $v \\in V(G)$, and we have to determine if there exists a list homomorphism $\\varphi$ from $(G,L)$ to $H$, i.e., an edge preserving mapping $\\varphi: V(G)\\to V(H)$ that satisfies $\\varphi(v)\\in L(v)$ for every $v\\in V(G)$. Note that if $H$ is the complete graph on $q$ vertices, the problem is equivalent to List $q$-Coloring. We investigate the kernelization properties of List $H$-Coloring parameterized by the vertex cover number of $G$: given an instance $(G,L)$ and a vertex cover of $G$ of size $k$, can we reduce $(G,L)$ to an equivalent instance $(G',L')$ of List $H$-Coloring where the size of $G'$ is bounded by a low-degree polynomial $p(k)$ in $k$? This question has been investigated previously by Jansen and Pieterse [Algorithmica 2019], who provided an upper bound, which turns out to be optimal if $H$ is a complete graph, i.e., for List $q$-Coloring. This result was one of the first applications of the method of kernelization via bounded-degree polynomials. We define two new integral graph invariants, $c^*(H)$ and $d^*(H)$, with $d^*(H) \\leq c^*(H) \\leq d^*(H)+1$, and show that for every graph $H$, List $H$-Coloring -- has a kernel with $\\mathcal{O}(k^{c^*(H)})$ vertices, -- admits no kernel of size $\\mathcal{O}(k^{d^*(H)-\\varepsilon})$ for any $\\varepsilon \u003e 0$, unless the polynomial hierarchy collapses. -- Furthermore, if $c^*(H) \u003e d^*(H)$, then there is a kernel with $\\mathcal{O}(k^{c^*(H)-\\varepsilon})$ vertices where $\\varepsilon \\geq 2^{1-c^*(H)}$. Additionally, we show that for some classes of graphs, including powers of cycles and graphs $H$ where $Δ(H) \\leq c^*(H)$ (which in particular includes cliques), the bound $d^*(H)$ is tight, using the polynomial method. We conjecture that this holds in general.","short_abstract":"For a fixed graph $H$, in the List $H$-Coloring problem, we are given a graph $G$ along with list $L(v) \\subseteq V(H)$ for every $v \\in V(G)$, and we have to determine if there exists a list homomorphism $\\varphi$ from $(G,L)$ to $H$, i.e., an edge preserving mapping $\\varphi: V(G)\\to V(H)$ that satisfies $\\varphi(v)\\...","url_abs":"https://arxiv.org/abs/2507.12005","url_pdf":"https://arxiv.org/pdf/2507.12005v2","authors":"[\"Marta Piecyk\",\"Astrid Pieterse\",\"Paweł Rzążewski\",\"Magnus Wahlström\"]","published":"2025-07-16T07:59:20Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}