Optimal data reduction for graph coloring using low-degree polynomials

DOI10.1007/s00453-019-00578-5zbMath1430.68128arXiv1802.02050OpenAlexW2942681663MaRDI 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 coloringgraph homomorphismkernelization

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ Unnamed Item ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Parameterized Complexity of Conflict-Free Graph Coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Data reduction for graph coloring problems
• List H-coloring a graph by removing few vertices
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On the complexity of H-coloring
• Efficient graph representations
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
• Point Line Cover
• Kernelization Lower Bounds by Cross-Composition
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
• Smaller Parameters for Vertex Cover Kernelization
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms

This page was built for publication: Optimal data reduction for graph coloring using low-degree polynomials