Improved hardness for H-colourings of G-colourable graphs

DOI10.1137/1.9781611975994.86zbMath1502.68136arXiv1907.00872OpenAlexW2955616642MaRDI QIDQ5146862

Marcin Wrochna, Stanislav Živný

Publication date: 2 February 2021

Published in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40) Graph theory (including graph drawing) in computer science (68R10) Relations of low-dimensional topology with graph theory (57M15) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (12)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

This page was built for publication: Improved hardness for H-colourings of G-colourable graphs