Improved hardness for H-colourings of G-colourable graphs
<p>We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems.</p> <p>First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bu...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Society for Industrial and Applied Mathematics
2020
|