Improved hardness for H-colourings of G-colourable graphs

Conference item

We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems.

First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bulín, Krokhin, and Opršal [STOC'19], who gave NP-hardness of colouring k-colourable graphs with 2k – 1 colours for k ≥ 3, and the result of Huang [APPROX-RANDOM'13], who gave NP-hardness of colouring k-colourable graphs with colours for sufficiently large k. Thus, for k ≥ 4, we improve from known linear/sub-exponential gaps to exponential gaps.

Second, we show that the topology of the box complex of H alone determines whether H-colouring of G-colourable graphs is NP-hard for all (non-bipartite, H-colourable) G. This formalises the topological intuition behind the result of Krokhin and Opršal [FOCS’19] that 3-colouring of G-colourable graphs is NP-hard for all (3-colourable, non-bipartite) G. We use this technique to establish NP-hardness of H-colouring of G-colourable graphs for H that include but go beyond K3, including square-free graphs and circular cliques (leaving K4 and larger cliques open).

Underlying all of our proofs is a very general observation that adjoint functors give reductions between promise constraint satisfaction problems.

The full version [55] containing detailed proofs is available at https://arxiv.org/abs/1907.00872.

Authors: Wrochna, M; Zivny, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA 2020)
• Journal: ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA 2020)
• Volume: 7
• Issue: 6
• Pages: 1426-1435
• Publication date: 2020-01-01
• Acceptance date: 2019-09-24
• DOI: 10.1137/1.9781611975994.86
• ISBN: 9781611975994
• Keywords: FFR