Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

DOI10.1007/978-3-319-57586-5_29zbMath1486.68083arXiv1701.06985OpenAlexW2580171847MaRDI QIDQ5283380

Bart M. P. Jansen, Lars Jaffke

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (16)

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ Structural parameterizations of clique coloring ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ List-coloring -- parameterizing from triviality ⋮ Parameterized (Approximate) Defective Coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Unnamed Item ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials ⋮ Computing the chromatic number using graph decompositions via matrix rank

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Data reduction for graph coloring problems
• Which problems have strongly exponential complexity?
• Parameterized complexity of vertex colouring
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Set Partitioning via Inclusion-Exclusion
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems