Abstract
Finding a proper coloring of a tcolorable graph G with t colors is a classic NPhard problem when t >= 3. In this work, we investigate the approximate coloring problem in which the objective is to find a proper ccoloring of G where c >= t. We show that for all t >= 3, it is NPhard to find a ccoloring when c <= 2t2. In the regime where t is small, this improves, via a unified approach, the previously best known hardness result of c <= max{2t 5, t + 2*floor(t/3)  1} (Garey and Johnson 1976; Khanna, Linial, Safra, 1993; Guruswami, Khanna, 2000). For example, we show that 6coloring a 4colorable graph is NPhard, improving on the NPhardness of 5coloring a 4colorable graph.
We also generalize this to related problems on the strong coloring of hypergraphs. A kuniform hypergraph H is tstrong colorable (where t >= k) if there is a tcoloring of the vertices such that no two vertices in each hyperedge of H have the same color. We show that if t = ceiling(3k/2), then it is NPhard to find a 2coloring of the vertices of H such that no hyperedge is monochromatic. We conjecture that a similar hardness holds for t=k+1.
We establish the NPhardness of these problems by reducing from the hardness of the Label Cover problem, via a "dictatorship test" gadget graph. By combinatorially classifying all possible colorings of this graph, we can infer labels to provide to the label cover problem. This approach generalizes the "weak polymorphism" framework of (Austrin, Guruswami, Hastad, 2014), though interestingly our results are "PCPfree" in that they do not require any approximation gap in the starting Label Cover instance.
BibTeX  Entry
@InProceedings{brakensiek_et_al:LIPIcs:2016:5829,
author = {Joshua Brakensiek and Venkatesan Guruswami},
title = {{New Hardness Results for Graph and Hypergraph Colorings}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {14:114:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5829},
URN = {urn:nbn:de:0030drops58291},
doi = {10.4230/LIPIcs.CCC.2016.14},
annote = {Keywords: hardness of approximation, graph coloring, hypergraph coloring, polymor phisms, combinatorics}
}
Keywords: 

hardness of approximation, graph coloring, hypergraph coloring, polymor phisms, combinatorics 
Collection: 

31st Conference on Computational Complexity (CCC 2016) 
Issue Date: 

2016 
Date of publication: 

19.05.2016 