<p>?? 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 <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow">basic property</a>:</p>

<blockquote>
  <p>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).\,$</p>
</blockquote>

<p>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.</p>

<p>[1] <a href="http://books.google.com/books/about/Cliques_Coloring_and_Satisfiability.html?id=-ysHoxUwdMUC" rel="nofollow">Cliques, coloring, &amp; satisfiability, 2nd DIMACS challenge</a></p>

<p>[2] <a href="http://dimacs.rutgers.edu/Volumes/Vol26.html" rel="nofollow">Dimacs vol 26: Cliques, coloring and satisfiability</a></p>

CC BY-SA 3.0
2012-11-20T19:54:42.877Z
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
CC BY-SA 3.0
2012-11-20T21:09:32.487Z
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
CC BY-SA 3.0
2012-11-20T21:17:29.063Z
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
CC BY-SA 3.0
2012-11-20T21:38:02.260Z
@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
CC BY-SA 3.0
2012-11-20T21:42:01.947Z
@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
CC BY-SA 3.0
2012-11-20T22:01:23.100Z
ok agreed the answer is only what might be called a "half reduction" ie as for false positives vs negatives it eliminates one but not the other. but it could be possibly used as half of a full reduction. the property seems central to the question... ie maybe one is looking for a generalization of the property... maybe an equality instead of an inequality? hazarded an answer given no others were given thinking something is better than nothing...
vzn
CC BY-SA 3.0
2012-11-20T22:13:57.330Z
another interesting factoid. for perfect graphs $\chi(G) = \omega(G)$. so maybe some conversion of the graph to a perfect graph construction & then calculating coloring/cliques on that....?
vzn
CC BY-SA 3.0
2012-11-20T23:40:26.003Z
further thought on this. [perfect graphs](http://en.wikipedia.org/wiki/Perfect_graph) are a broad class in some sense & include many other classes. $\chi(G), \omega(G)$ are solvable in Ptime for perfect graphs. so this seems to be a reasonable answer to the question for a broad class of graphs. (oops) for graphs outside it (imperfect), a P-time reduction to perfect graphs cannot be possible unless P=NP... anyway though perfect graphs seem to be somehow aligned with this question (research is ongoing...)
vzn
CC BY-SA 3.0
2012-11-21T05:15:14.760Z
also note recognition of perfect graphs is in P due to the CCLSV perfect graph theorem 2005
vzn
CC BY-SA 3.0
2012-11-20T18:29:19.043Z
2012-11-20T18:29:19.043Z
vzn
<p>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:</p>

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

<p>(2) Add one additional vertex $x$ to $H$.</p>

<p>(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'$.</p>

<p>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$.</p>

CC BY-SA 3.0
2012-11-21T21:35:25.820Z
This is wonderful.
William Macrae
CC BY-SA 3.0
2012-11-26T06:51:04.270Z
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
CC BY-SA 3.0
2012-11-26T07:37:09.220Z
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
CC BY-SA 3.0
2012-11-26T07:44:02.930Z
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
CC BY-SA 3.0
2012-11-26T07:47:15.587Z
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
CC BY-SA 4.0
2020-01-24T08:26:00.717Z
As suggested by WilliamMacrae, the last sentence can be written as follows. The clique in $G$ can be recovered from a coloring of $H$ as the set of vertices $v$ for which there is an $i\leq k$ such that $(v,i)$ has the same color as $x$.
Cyriac Antony
CC BY-SA 3.0
2012-11-21T21:07:54.920Z
2012-11-21T21:17:07.690Z
2012-11-21T21:17:07.690Z
David Eppstein
<p>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.</p>

<p>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'$.</p>

<p><strong>Edit</strong>: To add some brief motivation, Karp's <a href="http://www.cs.berkeley.edu/~luca/cs172/karp.pdf">original 21 problems</a> 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?</p>

<p><strong>Edit 2</strong>: 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).</p>

<p>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 &gt; 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.</p>

<p>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.</p>

<p>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?</p>

<p><strong>Edit 3</strong>: 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.</p>

CC BY-SA 3.0
2012-11-15T02:10:29.533Z
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
CC BY-SA 3.0
2012-11-15T02:40:57.093Z
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
CC BY-SA 3.0
2012-11-19T09:08:16.907Z
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.
John K.
CC BY-SA 3.0
2012-11-19T18:11:33.920Z
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
CC BY-SA 3.0
2012-11-19T20:15:06.017Z
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
CC BY-SA 3.0
2012-11-19T22:01:18.523Z
Oops, the above should start "it's easier to show $\chi(G)=4$ than 3..." And I can't find an edit button from my phone.
William Macrae
<cc.complexity-theory><graph-theory><np-hardness><reductions>
Natural CLIQUE to k-Color reduction
William Macrae
# Natural CLIQUE to k-Color reduction

(Asked by: username_0 on 2012-11-14)

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](http://www.cs.berkeley.edu/~luca/cs172/karp.pdf) 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.

**Tags:** cc.complexity-theory, graph-theory, np-hardness, reductions

> **Comments:**
> **username_1**: 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  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: 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!)  
> **username_0**: 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$.  
> **username_0**: Oops, the above should start "it's easier to show $\chi(G)=4$ than 3..." And I can't find an edit button from my phone.  

---

## 2 answers

### Answer by username_6 on 2012-11-21. Score: 16 | Accepted answer

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$.

> **Comments:**
> **username_0**: This is wonderful.  
> **username_0**: 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!  
> **username_6**: 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.  
> **username_0**: 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).  
> **username_0**: 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.  
> **username_7**: As suggested by WilliamMacrae, the last sentence can be written as follows. The clique in $G$ can be recovered from a coloring of $H$ as the set of vertices $v$ for which there is an $i\leq k$ such that $(v,i)$ has the same color as $x$.  

---

### Answer by username_4 on 2012-11-20. Score: -8

?? 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](http://en.wikipedia.org/wiki/Graph_coloring):

> 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.

[1] [Cliques, coloring, & satisfiability, 2nd DIMACS challenge](http://books.google.com/books/about/Cliques_Coloring_and_Satisfiability.html?id=-ysHoxUwdMUC)

[2] [Dimacs vol 26: Cliques, coloring and satisfiability](http://dimacs.rutgers.edu/Volumes/Vol26.html)

> **Comments:**
> **username_5**: 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$).  
> **username_4**: 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....  
> **username_0**: 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.  
> **username_5**: @username_4: 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.  
> **username_5**: @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.  
> **username_4**: ok agreed the answer is only what might be called a "half reduction" ie as for false positives vs negatives it eliminates one but not the other. but it could be possibly used as half of a full reduction. the property seems central to the question... ie maybe one is looking for a generalization of the property... maybe an equality instead of an inequality? hazarded an answer given no others were given thinking something is better than nothing...  
> **username_4**: another interesting factoid. for perfect graphs $\chi(G) = \omega(G)$. so maybe some conversion of the graph to a perfect graph construction & then calculating coloring/cliques on that....?  
> **username_4**: further thought on this. [perfect graphs](http://en.wikipedia.org/wiki/Perfect_graph) are a broad class in some sense & include many other classes. $\chi(G), \omega(G)$ are solvable in Ptime for perfect graphs. so this seems to be a reasonable answer to the question for a broad class of graphs. (oops) for graphs outside it (imperfect), a P-time reduction to perfect graphs cannot be possible unless P=NP... anyway though perfect graphs seem to be somehow aligned with this question (research is ongoing...)  
> **username_4**: also note recognition of perfect graphs is in P due to the CCLSV perfect graph theorem 2005  

---

