Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with coloring:
TR95-033 | 29th June 1995
Richard Beigel, David Eppstein

3-Coloring in time O(1.3446^n): a no-MIS algorithm

We consider worst case time bounds for NP-complete problems
including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.
Our algorithms are based on a common generalization of these problems,
called symbol-system satisfiability or, briefly, SSS [R. Floyd &
R. Beigel, The Language of Machines]. 3-SAT is equivalent to
(2,3)-SSS while the other problems ... more >>>

TR05-039 | 13th April 2005
Irit Dinur, Elchanan Mossel, Oded Regev

Conditional Hardness for Approximate Coloring

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

TR14-051 | 12th April 2014
Subhash Khot, Rishi Saket

Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a ... more >>>

ISSN 1433-8092 | Imprint