A near-optimal kernel for a coloring problem

DOI10.1016/J.DAM.2025.06.065MaRDI QIDQ6928018zbMATH OpenFDO

Authors Ishay Haviv, Dror Rabinovich

Publication date 17 September 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.06.065

zbMATH Keywords

graph coloringkernelizationlinear algebraparameterized complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Best-case and worst-case sparsifiability of Boolean CSPs
• Data reduction for graph coloring problems
• Graph-Theoretic Concepts in Computer Science
• Kernelization. Theory of parameterized preprocessing
• Optimal data reduction for graph coloring using low-degree polynomials
• Optimal polynomial-time compression for Boolean Max CSP
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Parameterized complexity of vertex colouring
• Some consequences of non-uniform conditions on uniform classes

This page was built for publication: A near-optimal kernel for a coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6928018)