# Natural CLIQUE to k-Color reduction

There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. What I'm wondering is whether there is a reasonable direct reduction between these problems. Say, a reduction that I could explain to a friend fairly briefly without needing to describe an intermediate language like SAT.

As an example of what I'm looking for, here's a direct reduction in the reverse direction: Given G with $n$ and some $k$ (the number of colors), make a graph G' with $kn$ vertices (one per color per vertex). The vertices $v'$, $u'$ corresponding to vertices $v, u$ and colors $c, d$ respectively are adjacent if and only if $v \neq u$ and ($c \neq d$ or $vu \not \in G$). An $n$-clique in $G'$ has only one vertex per vertex in $G$, and the corresponding colors are a proper $k$-coloring of $G$. Similarly, any proper $k$-coloring of $G$ has a corresponding clique in $G'$.

Edit: To add some brief motivation, Karp's original 21 problems are proved NP-Complete by a tree of reductions where CLIQUE and Chromatic Number form the roots of major subtrees. There are some natural reductions between problems in the the CLIQUE subtree and the Chromatic Number subtree, but many of them are just as hard to find as the one I'm asking about. I'm trying to drill down on whether the structure of this tree shows some underlying structure in the other problems or if it is entirely a consequence of which reductions were found first, since there is less motivation to search for reductions between two problems when they are known to be in the same complexity class. Certainly the order had some influence, and parts of the tree can be rearranged, but can it be rearranged arbitrarily?

Edit 2: I continue to search for a direct reduction, but here is a sketch of the closest I've gotten (it should be a valid reduction, but has CIRCUIT SAT as a clear intermediary; it's somewhat subjective whether this is any better than composing two reductions as alluded to in the first paragraph).

Given $G, k$, we know that $\overline{G}$ can be $n-k+1$-colored with $k$ vertices all colored True iff $G$ has a $k$-clique. We name the original vertices of $G$ $v_1, \ldots, v_n$ and then add to $\overline G$ additional vertices: $C_{ij}$ with $1 \le i \le n$, $0 \le j \le k$. The key invariant will be that $C_{ij}$ can be colored True if and only if among vertices $\{v_1,\ldots, v_i\}$ there are at least $j$ vertices colored True. So, each $C_{i0}$ can be True. Then, $C_{ij}$ for $j > 0$ gets the color $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ where all non-true colors are treated as false. There is a $k$-clique in $G$ iff $C_{nk}$ can be colored True, so if we force that coloring, the new graph is colorable iff there was a $k$-clique in the original graph.

The AND and OR gadgets to enforce the relationships are much like the reduction from CIRCUIT SAT to 3-COLOR, but here we include a $K_{n-k+1}$ in our graph, pick vertices T, F, and Ground, and then connect all others to everything but the $v_i$s; this assure that the $C_{ij}$s and the other gadgets receive only 3 colors.

Anyway, the $\overline G$ part of this reduction feels direct, but the use of AND/OR gates is much less direct. The question remains, is there a more elegant reduction?

Edit 3: There have been a few comments about why this reduction would be hard to find. CLIQUE and k-Color are indeed quite different problems. Even without a reduction, though, an answer that details why the reduction is hard in the one direction but possible in the other would be very helpful and contribute a lot to the problem.

• The kind of direct reduction you are looking for might be difficult to find since Clique and coloring are kind of opposite in the sense that a 1-clique is as easy to find as an n-coloring. So maybe the reduction should be of the form: $G'$ has an $n-k$-coloring if and only if $G$ has a $k$-clique – Martin Vatshelle Nov 15 '12 at 2:10
• I agree that it is difficult; this is the reason for my interest; I'll give detail on motivation in the question. The $n-k$-coloring idea has gotten me the closest. If there is a $k$-clique in $G$ then $\overline{G}$ may have all vertices in the clique monochromatic because they are an independent set. The problem is that the chromatic number of the rest can vary. Linking two vertices to a $K_{n-k-1}$ forces them to have the same color, but I have no idea which set of vertices to force. A gadget that forces some $i$ out of $j$ vertices to be monochromatic would do it. – William Macrae Nov 15 '12 at 2:40
• I agree with Martin here that this might not even be doable (without going via, say 3SAT). Clique and coloring have very little in common. I want therefore to recall the theorem of Erdős, given naturals g and k, there is a graph with girth at least g and chromatic number at least k (think about that for a while if you aren't familiar with it). Finally, your reduction must also be aware that while Clique (and Independent Set) is in $W[1]$ parameterized by solution set, there is no equivalent parameterization for the chromatic number of a graph. – Pål GD Nov 19 '12 at 9:08
• I do not understand @MartinVatshelle's comment. As far as I know, all 1-clique, 1-coloring, n-clique, and n-coloring are trivial at the same level. (don't think you can always answer the 1-clique by YES: the input graph might be empty!) – Yixin Cao Nov 19 '12 at 18:11
• I think Martin's point is it's show $\chi(G)=4$ and $\chi(G)=3$, but harder to find a $K_4$ than a $K_3$. So there is a bit of duality to the two concepts. @PålGD's point about Erdős's theorem is a great one (and I love that theorem), as graphs with large girth have large independence number, and so their inverses will have large cliques. Overall it feels like there's a trap here though, which is to relate Cliques and Colorings in the same or similar graphs, but as with the reverse direction the reduction might construct a very different graph than $G$. – William Macrae Nov 19 '12 at 20:15

Given a graph $G$ and a number $k$, such that you want to know whether $G$ contains a $k$-clique, let n be the number of vertices in $G$. We construct another graph $H$, such that $H$ is $n$-colorable if and only if $G$ has a $k$-clique, as follows:

(1) For each vertex $v$ in $G$, make an $n$-clique of vertices $(v,i)$ in $H$, where $i$ ranges from $1$ to $n$.

(2) Add one additional vertex $x$ to $H$.

(3) For each triple $\{x,y,z\}$ of vertices in $H$, where $y=(v,i)$ and $z=(u,j)$, test whether one of the following conditions holds: either $u\ne v$ and $i=j$, or $u$ and $v$ are nonadjacent vertices in $G$ with $\max(i,j)\le k$. If either of these two things is true, add another $n$-clique to $H$. Within this clique, select three vertices $x'$, $y'$, and $z'$. Connect $x$ to every vertex in the clique except for $y'$ and $z'$; connect $y$ to every vertex in the clique except for $x'$ and $z'$; and connect $z$ to every vertex in the clique except for $x'$ and $y'$.

The gadgets added in step (3) prevent the triple of vertices $x$, $y$, and $z$ from all being given the same color as each other in a valid coloring of $H$. The clique in $G$ can be recovered from a coloring of $H$ as the set of vertices $(v,i)$ that are in the same color class as $x$ and that have $i\le k$.

• This is wonderful. – William Macrae Nov 21 '12 at 21:35
• For some reason my edit was rejected, but the last sentence should describe vertices of G rather than H (since it is intended to describe a clique in G). Something like "The clique in $G$ can be recovered from a coloring of H as $\{v : \exists i \le k \chi((v,i)) = \chi(x) \}.$" Also, I forgot to say thanks for the answer, it's been very helpful! – William Macrae Nov 26 '12 at 6:51
• Sure, you could put in another clause to that sentence about stripping off the $i$ from each pair, but I thought that step was easy enough to omit, and my general feeling is that (when it can be kept short enough) prose tends to be more readable than a formula. – David Eppstein Nov 26 '12 at 7:37
• I agree that prose are more preferable. Maybe just adding a phrase like "the first coordinate of each (v,i)..." is idea. The reason for my concern about the technicality is that when first reading reductions it can be hard to keep straight the exact definitions of the elements in the first language and the second, and which is which. The minute something appears to break a definition, it can throw me for a loop. If I had trouble understanding previous sentences and got to the last one, I would determine that G and H have vertices of the form (v,i). – William Macrae Nov 26 '12 at 7:44
• I should also say that I think you've done a much better job talking through this reduction than almost any other that I've read. There's a problem in the literature that many reductions are stated formally with no motivation or intuition, and you've avoided that very nicely. – William Macrae Nov 26 '12 at 7:47

?? coloring and clique finding have been known to be tightly coupled for decades via graph theory (possibly even in the 60s?) even not through SAT as an intermediary (which became typical after the Cook proof in 1971). believe there are algorithms based on the following basic property:

If G contains a clique of size k, then at least k colors are needed to color that clique; in other words, the chromatic number is at least the clique number: $\chi(G) \ge \omega(G).\,$

not sure of exact refs but [1,2] are good places to start, an exact algorithm or ref is at least likely cited in these books.

• Using the property $\chi(G) \geq \omega(G)$, you can invoke an algorithm for $k-COLORABILITY$ on $G$: if the algorithm returns $YES$, then $G$ does not contain any clique of size at least $k+1$. However the opposite implication does not hold: if the algorithm returns $NO$, then $G$ may or may not have a clique of size at least $k+1$ (as a counterexample, consider a pyramid whose polygonal base has an odd number of vertices: it is not $3$-colorable, however it has not any clique of size at least $4$). – Giorgio Camerani Nov 20 '12 at 19:54
• yes, agreed; as I interpret it the original post was not insistent on the direction of the reduction but more emphasized avoiding SAT as the intermediary, asking for a "fairly brief explanation". also conspicuously nobody mentioned the above factoid so far.... the question & comments also seem to inaccurately indicate in various ways the two problems are not tightly coupled.... – vzn Nov 20 '12 at 21:09
• Apologies if the direction was ambiguous. I am interested in a correct reduction (YES $\iff$ YES), and I am interested in a reduction from Clique to k-Color. I have the other direction and it is explained in my post. There are certainly many things that relate cliques in graphs to colorings in graphs and vice versa, and indeed I have seen many of them (and I assume many others here have seen many of them), but I'm really interested exclusively in a direct reduction or a convincing explanation of why it might not exist. – William Macrae Nov 20 '12 at 21:17
• @vzn: My comment was not meant to criticize your answer. Truth be told, initially I made a reasoning similar to yours, but then I realized that, if the opposite implication would have hold, then $3-COLORING$ on general graphs, which is known to be NP-complete, would have been solvable trivially by just checking whether the input graph had a clique of $4$ nodes: any $G$ would have been $3$-colorable if and only if it does not contain any clique of size $4$ (that's plain false, of course, as the pyramid counterexample shows). By the way: I'm not the one who downvoted. – Giorgio Camerani Nov 20 '12 at 21:38
• @WilliamMacrae: It was perfectly clear that you wanted a $\Longleftrightarrow$ reduction, otherwise it wouldn't have been a reduction! Also, it was perfectly clear that you wanted a reduction from $CLIQUE$ to $COLORING$ and not the other way. – Giorgio Camerani Nov 20 '12 at 21:42