Optimal data reduction for graph coloring using low-degree polynomials

DOI10.1007/s00453-019-00578-5zbMath1430.68128arXiv1802.02050MaRDI QIDQ2272594

Bart M. P. Jansen, Astrid Pieterse

Publication date: 10 September 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.02050

zbMATH Keywords

graph coloring; graph homomorphism; kernelization

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68Q27: Parameterized complexity, tractability and kernelization