Improved hardness for H-colourings of G-colourable graphs

Marcin Wrochna, Stanislav Živný

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…