<p>The main point of considering the Multicolored Clique problem is that the input of Multicolored Clique already comes with a <span class="math-container">$k$</span>-coloring which facilitates parameterized reductions to other problems. For example, one may assume then that the maximum clique size does not exceed <span class="math-container">$k$</span> and that the size-<span class="math-container">$k$</span> clique, if it exists, contains exactly one vertex from each color class.</p>
<p>Now concerning the necessity of providing a reduction from Clique to Multicolored Clique: Yes, the clique number <span class="math-container">$k$</span> is a lower bound on the coloring number but they are not necessarily the same. So a priori, it could still be the case that Clique is W[1]-hard with respect to the clique size <span class="math-container">$k$</span> in general but FPT with respect to <span class="math-container">$k$</span> in <span class="math-container">$k$</span>-colorable graphs. The reduction shows that the latter case is also W[1]-hard.</p>

CC BY-SA 4.0
2024-06-27T13:32:31.563Z
2024-06-27T13:32:31.563Z
Christian Komusiewicz
<p>I do not understand why we need to make a reduction from k-clique to k-multicoloured clique.
Any k-clique can only be coloured in k different colours since each pair of vertices is adjacent. So it already induces a k-colouring.
What am I missing?</p>
<p>Thanks!</p>

CC BY-SA 4.0
2024-06-27T09:46:15.100Z
This question is incomprehensible without context. Who, where, is making a reduction from $k$-clique to $k$-multicoloured clique?
Emil Jeřábek
CC BY-SA 4.0
2024-06-27T10:41:06.013Z
I am reading a course at university about parametrised algorithms. On the slides they talk about an FTP reduction from clique to k-colouring. They clone every node within the graph k times one for each colour and add edges between nodes that are adjacent in the original graph and of different colour in the new cloned graph. I do not know if I missed something.
peterparker
<graph-theory><np-hardness><graph-colouring><clique>
why is there the need for a reduction between clique and multicoloured clique?
peterparker
# why is there the need for a reduction between clique and multicoloured clique?

(Asked by: username_0 on 2024-06-27)

I do not understand why we need to make a reduction from k-clique to k-multicoloured clique.
Any k-clique can only be coloured in k different colours since each pair of vertices is adjacent. So it already induces a k-colouring.
What am I missing?

Thanks!

**Tags:** graph-theory, np-hardness, graph-colouring, clique

> **Comments:**
> **username_1**: This question is incomprehensible without context. Who, where, is making a reduction from $k$-clique to $k$-multicoloured clique?  
> **username_0**: I am reading a course at university about parametrised algorithms. On the slides they talk about an FTP reduction from clique to k-colouring. They clone every node within the graph k times one for each colour and add edges between nodes that are adjacent in the original graph and of different colour in the new cloned graph. I do not know if I missed something.  

---

## 1 answers

### Answer by username_2 on 2024-06-27. Score: 5

The main point of considering the Multicolored Clique problem is that the input of Multicolored Clique already comes with a $k$-coloring which facilitates parameterized reductions to other problems. For example, one may assume then that the maximum clique size does not exceed $k$ and that the size-$k$ clique, if it exists, contains exactly one vertex from each color class.

Now concerning the necessity of providing a reduction from Clique to Multicolored Clique: Yes, the clique number $k$ is a lower bound on the coloring number but they are not necessarily the same. So a priori, it could still be the case that Clique is W[1]-hard with respect to the clique size $k$ in general but FPT with respect to $k$ in $k$-colorable graphs. The reduction shows that the latter case is also W[1]-hard.


---

