Optimal data reduction for graph coloring using low-degree polynomials

Bart M.P. Jansen, Astrid Pieterse

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
67 Downloads (Pure)


The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we use a recent technique of finding redundant constraints by representing them as lowdegree polynomials, to obtain a kernel of bitsize O(kq-1 log k) for q-Coloring parameterized by Vertex Cover for any q ≥ 3. This size bound is optimal up to ko(1) factors assuming NP ⊈ coNP/poly, and improves on the previous-best kernel of size O(kq). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP ⊈ coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n2-ϵ) for any ϵ > 0. Previously, such a lower bound was only known for coloring with q ≥ 4 colors.

Original languageEnglish
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)978-3-95977-051-4
Publication statusPublished - 1 Feb 2018
Event12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria
Duration: 6 Sep 20178 Sep 2017
Conference number: 12

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)


Conference12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Abbreviated titleIPEC 2017
Internet address


  • Graph coloring
  • Kernelization
  • Sparsification


Dive into the research topics of 'Optimal data reduction for graph coloring using low-degree polynomials'. Together they form a unique fingerprint.

Cite this