Conference item icon

Conference item

Improved hardness for H-colourings of G-colourable graphs

Abstract:

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 gra...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1137/1.9781611975994.86

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0002-0263-159X
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA 2020) Journal website
Volume:
7
Issue:
6
Pages:
1426-1435
Host title:
ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA 2020)
Publication date:
2020-01-01
Acceptance date:
2019-09-24
DOI:
Source identifiers:
1059974
ISBN:
9781611975994
Keywords:
Pubs id:
pubs:1059974
UUID:
uuid:573a79ed-831e-4f29-8092-7f7bdff8e972
Local pid:
pubs:1059974
Deposit date:
2019-10-03

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP