2025/07/16 by Marta Piecyk, Astrid Pieterse, Piecyk, Marta +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2507.12005
openalex publication_date 2025/07/16 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
For a fixed graph H, in the List H-Coloring problem, we are given a graph G along with list L(v) ⊆ V(H) for every v ∈ V(G), and we have to determine if there exists a list homomorphism φ from (G,L) to H, i.e., an edge preserving mapping φ: V(G)→ V(H) that satisfies φ(v)∈ L(v) for every v∈ 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) ≤ c^*(H) ≤ d^*(H)+1, and show that for every graph H, List H-Coloring -- has a kernel with O(kc^*(H)) vertices, -- admits no kernel of size O(kd^*(H)-ε) for any ε > 0, unless the polynomial hierarchy collapses. -- Furthermore, if c^*(H) > d^*(H), then there is a kernel with O(kc^*(H)-ε) vertices where ε ≥ 21-c^*(H). Additionally, we show that for some classes of graphs, including powers of cycles and graphs H where Δ(H) ≤ c^*(H) (which in particular includes cliques), the bound d^*(H) is tight, using the polynomial method. We conjecture that this holds in general.