2025/04/16 by Ishay Haviv, Haviv, Ishay, D. Rabinovich +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Scheduling and Timetabling Solutions #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2504.12281
For a fixed integer q, the q-Coloring problem asks to decide if a given graph has a vertex coloring with q colors such that no two adjacent vertices receive the same color. In a series of papers, it has been shown that for every q ≥ 3, the q-Coloring problem parameterized by the vertex cover number k admits a kernel of bit-size \widetildeO(kq-1), but admits no kernel of bit-size O(kq-1-ε) for ε >0 unless NP ⊆ coNP/poly (Jansen and Kratsch, 2013; Jansen and Pieterse, 2019). In 2020, Schalken proposed the question of the kernelizability of the q-Coloring problem parameterized by the number k of vertices whose removal results in a disjoint union of edges and isolated vertices. He proved that for every q ≥ 3, the problem admits a kernel of bit-size \widetildeO(k2q-2), but admits no kernel of bit-size O(k2q-3-ε) for ε >0 unless NP ⊆ coNP/poly. He further proved that for q ∈ \3,4\ the problem admits a near-optimal kernel of bit-size \widetildeO(k2q-3) and asked whether such a kernel is achievable for all integers q ≥ 3. In this short paper, we settle this question in the affirmative.