Data Reduction for Graph Coloring Problems

DOI10.1007/978-3-642-22953-4_8zbMath1342.68167arXiv1104.4229OpenAlexW2962964261MaRDI QIDQ3088272

Bart M. P. Jansen, Stefan Kratsch

Publication date: 19 August 2011

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

On the Hardness of Losing Width ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ On the hardness of losing width ⋮ On cutwidth parameterized by vertex cover ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of some colorful problems parameterized by treewidth
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Some consequences of non-uniform conditions on uniform classes
• Parameterized coloring problems on chordal graphs
• On problems without polynomial kernels
• Axioms and hulls
• Scheduling with incompatible jobs
• Parameterized complexity of vertex colouring
• Edge dominating set and colorings on graphs with fixed clique-width
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Intractability of Clique-Width Parameterizations
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Graph colorings with local constraints -- a survey
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Data Reduction for Graph Coloring Problems