Paper Info
Title
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
Abstract
For 3 ≤ q Q we consider the ApproxColoring(q,Q) problem of deciding whether χ(G) ≤ q or χ(G) ≥ Q for a given graph G. Hardness of this problem was shown in [7] for q = 3,4 and arbitrary large constant Q under variants of the Unique Games Conjecture [10]. We extend this result to values of Q that depend on the size of a given graph. The extension depends on the parameters of the conjectures we consider. Following the approach of [7], we find that a careful calculation of the parameters gives hardness of coloring a 4-colorable graph with lgc(lg(n))\lg^c(\lg(n)) colors for some constant c > 0. By improving the analysis of the reduction we show that under related conjectures it is hard to color a 4-colorable graph with lgc(n)\lg^c(n) colors for some constant c > 0. The main technical contribution of the paper is a variant of the Majority is Stablest Theorem, which says that among all balanced functions whose each coordinate has o(1) influence, the Majority function has the largest noise stability. We adapt the theorem for our applications to get a better dependency between the parameters required for the reduction.
Year
DOI
Venue
2013
10.1007/978-3-642-15369-3_11
Electronic Colloquium on Computational Complexity (ECCC)
Keywords
Field
DocType
constant c,stablest theorem,super-constant number,conditional hardness,unique games conjecture,arbitrary large constant q,q q,4-colorable graph,better dependency,balanced function,majority function,graph g. hardness,graph coloring,hardness of approximation
Discrete mathematics,Complete coloring,Edge coloring,Combinatorics,Graph power,Fractional coloring,List coloring,Cubic graph,Graph minor,Mathematics,Graph coloring
Journal
Volume
ISBN
Citations 
20
3-642-15368-2
6
PageRank 
References 
Authors
0.48
9
2
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Igor Shinkar2248.97