The complexity of 3-colouring H-colourable graphs

DOI10.1109/FOCS.2019.00076MaRDI QIDQ6944161zbMATH OpenFDO

Authors Andrei Krokhin, Jakub Opršal

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2019.00076

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(7)

• The complexity of promise SAT on non-Boolean domains
• Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
• Local consistency as a reduction between constraint satisfaction problems
• Injective hardness condition for PCSPs
• Symmetric promise constraint satisfaction problems: beyond the Boolean case
• Conditional dichotomy of Boolean ordered promise CSPs
• Beyond PCSP (1-in-3, NAE)

This page was built for publication: The complexity of 3-colouring \(\mathbf{H}\)-colourable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6944161)