2002/11/19 by Martin Fürer · 32 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Combinatorics #Chromatic scale #Mathematics #Exponent #Discrete mathematics #Graph
paper · doi:10.1109/sfcs.1995.492572
openalex publication_date 2002/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
First, a simplified geometric proof is presented for the result of C. Lund and M. Yannakakis (1994) saying that for some /spl epsiv/>0 it is NP-hard to approximate the chromatic number of graphs with N vertices by a factor of N/sup /spl epsiv//. Then, more sophisticated techniques are employed to improve the exponent. A randomized twisting method allows us to completely pack a certain space with copies of a graph without much affecting the independence number. Together with the newest results of M. Bellare et al. (1995), on the number of amortized free bits, it is shown that for every /spl epsiv/>0 the chromatic number cannot be approximated by a factor of N/sup 1/5-/spl epsiv// unless NP=ZPP. Finally, we get polynomial lower bounds in terms of /spl chi/. Unless NP=ZPP, the performance ratio of every polynomial time algorithm approximating the chromatic number of /spl chi/-colorable graphs (i.e., the chromatic number is at most /spl chi/) is at least /spl chi//sup 1/5-o(1/) (where the o-notation is with respect to /spl chi/).