New hardness results for graph and hypergraph colorings
From MaRDI portal
Publication:5368748
DOI10.4230/LIPIcs.CCC.2016.14zbMath1380.68190OpenAlexW2472217601MaRDI QIDQ5368748
Joshua Brakensiek, Venkatesan Guruswami
Publication date: 10 October 2017
Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2016.14
Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (17)
Topology and Adjunction in Promise Constraint Satisfaction ⋮ Vertex isoperimetry and independent set stability for tensor powers of cliques ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Unnamed Item ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ $(2+\varepsilon)$-Sat Is NP-hard ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Unnamed Item ⋮ Approximately coloring graphs without long induced paths ⋮ Unnamed Item ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
This page was built for publication: New hardness results for graph and hypergraph colorings
