<p>I followed the link in the question, and the reduction there actually produces graphs whose edges have a natural coloring such that each <span class="math-container">$K_n$</span> present in the graph is a "rainbow <span class="math-container">$K_n$</span>" (has exactly one edge of each color). In other words, we can easily adjust the reduction in that paper so that it reduces to your problem instead of reducing to the partition into <span class="math-container">$K_n$</span>s problem: simply assign each edge a color according to this natural coloring and then the graph can be partitioned into "rainbow <span class="math-container">$K_n$</span>s" if and only if it could be partitioned into <span class="math-container">$K_n$</span>s at all.</p>

<p>The basic structure of the reduction in that paper can be accomplished with the following 3 steps:</p>

<ol>
<li>Create many copies of a particular graph <span class="math-container">$H_{n,p}$</span>.</li>
<li>Identify certain pieces of some copies of <span class="math-container">$H_{n,p}$</span> with each other (i.e. merge vertices/edges between multiple different copies of <span class="math-container">$H_{n,p}$</span>).</li>
<li>Remove certain vertices/edges from some copies.</li>
</ol>

<p>The graph <span class="math-container">$H_{n,p}$</span> has as its vertices the set of length-<span class="math-container">$n$</span> vectors modulo <span class="math-container">$p$</span> for which the components add to <span class="math-container">$0$</span> mod <span class="math-container">$p$</span>. The edges connect every two vertices that differ in only two components with differences of <span class="math-container">$+1$</span> and <span class="math-container">$-1$</span> in those two components.</p>

<p>I propose the following coloring for this graph: assign a color to each edge according to its direction. If <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are adjacent vertices, then <span class="math-container">$x-y$</span> is a vector with <span class="math-container">$n-2$</span> components equal to <span class="math-container">$0$</span>, one component equal to <span class="math-container">$1$</span> and one component equal to <span class="math-container">$-1$</span>. In other words, for every edge <span class="math-container">$(x, y)$</span> there are <span class="math-container">${n \choose 2}$</span> options for which components of <span class="math-container">$x-y$</span> are non-zero. If we assign a unique color to each of these options then we have a coloring for all the edges such that every edge in the same direction has the same color. It is pretty easy to verify that no two edges in a <span class="math-container">$K_n$</span> in <span class="math-container">$H_{n,p}$</span> are in the same direction. Therefore every <span class="math-container">$K_n$</span> in <span class="math-container">$H_{n,p}$</span> is a rainbow <span class="math-container">$K_n$</span> under this coloring.</p>

<p>When we follow the reduction, we use this coloring for every copy of <span class="math-container">$H_{n,p}$</span>. Therefore at the end of step 1 in the list above, every <span class="math-container">$K_n$</span> in the graph is a rainbow <span class="math-container">$K_n$</span>.</p>

<p>In step 2 of the above list, we identify some vertices/edges with each other. In particular, in the reduction we always identify a <span class="math-container">$K_n$</span> with another <span class="math-container">$K_n$</span>. But in this situation (where all the <span class="math-container">$K_n$</span>s are from a copy of <span class="math-container">$H_{n,p}$</span>), every <span class="math-container">$K_n$</span> is either a translation of the "standard <span class="math-container">$K_n$</span>" which the paper calls <span class="math-container">$K$</span> or a translation of <span class="math-container">$-K$</span>. Therefore, we are either identifying two parallel <span class="math-container">$K_n$</span>s or two <span class="math-container">$K_n$</span>s that are "flips" of each other. In either case, the edges that are identified across the two <span class="math-container">$K_n$</span>s are parallel and are therefore the same color. For example, see Figure 2 in the paper; edges that are identified are always parallel. Thus, since we never try to identify two edges of different colors, the coloring at the end of step 1 in the above list can be naturally extended into a coloring at the end of step 2. Identifying certain vertices/edges together doesn't create any new <span class="math-container">$K_n$</span>s, so it is still the case at the end of this step that every <span class="math-container">$K_n$</span> is a rainbow <span class="math-container">$K_n$</span>.</p>

<p>Finally in step 3 we remove some vertices/edges, which also doesn't create any new <span class="math-container">$K_n$</span>s. Thus, we have our desired property: under the coloring I provided, every <span class="math-container">$K_n$</span> in the graph generated by this reduction is a rainbow <span class="math-container">$K_n$</span>.</p>

CC BY-SA 4.0
2019-01-18T09:08:09.447Z
2019-01-18T09:08:09.447Z
Mikhail Rudoy
<p>I'm wondering if the following problem is NP-hard.</p>

<blockquote>
  <p><strong>Input:</strong> $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges 
  ($f$ does not verify any specific property).</p>
  
  <p><strong>Question:</strong> is it possible to partition $E$ into $|E|/3$ triangles, 
  such that each triangle has one edge of each color?</p>
</blockquote>

<p>I know that without the colors the problem of "edge partitioning" a graph into 
$K_n$, $n \geq 3$ is NP-hard 
(see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.6042&amp;rep=rep1&amp;type=pdf">The NP-Completeness of Some Edge-Partition Problems</a>)
but with the colors I don't know.</p>

<p>I would also be interested in a result for edge partitioniong into rainbow $K_c$, with $c$ a constant. Of course, in this case the problem becomes:</p>

<blockquote>
  <p><strong>Input:</strong> $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,\ldots,c(c-1)/2\}$ of the edges ($f$ does not verify any specific property).</p>
  
  <p><strong>Question:</strong> is it possible to partition $E$ into $|E|/(c(c-1)/2)$ $K_c$'s, 
  such that each clique $K_c$ has one edge of each color?</p>
</blockquote>

<graph-theory><np-hardness>
Edge-partitioning into rainbow triangles
user32018
# Edge-partitioning into rainbow triangles

(Asked by: username_0 on 2015-05-26)

I'm wondering if the following problem is NP-hard.

> **Input:** $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges
> ($f$ does not verify any specific property).
>
> **Question:** is it possible to partition $E$ into $|E|/3$ triangles,
> such that each triangle has one edge of each color?

I know that without the colors the problem of "edge partitioning" a graph into
$K\_n$, $n \geq 3$ is NP-hard
(see [The NP-Completeness of Some Edge-Partition Problems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.6042&rep=rep1&type=pdf))
but with the colors I don't know.

I would also be interested in a result for edge partitioniong into rainbow $K\_c$, with $c$ a constant. Of course, in this case the problem becomes:

> **Input:** $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,\ldots,c(c-1)/2\}$ of the edges ($f$ does not verify any specific property).
>
> **Question:** is it possible to partition $E$ into $|E|/(c(c-1)/2)$ $K\_c$'s,
> such that each clique $K\_c$ has one edge of each color?

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


---

## 1 answers

### Answer by username_1 on 2019-01-18. Score: 1

I followed the link in the question, and the reduction there actually produces graphs whose edges have a natural coloring such that each $K\_n$ present in the graph is a "rainbow $K\_n$" (has exactly one edge of each color). In other words, we can easily adjust the reduction in that paper so that it reduces to your problem instead of reducing to the partition into $K\_n$s problem: simply assign each edge a color according to this natural coloring and then the graph can be partitioned into "rainbow $K\_n$s" if and only if it could be partitioned into $K\_n$s at all.

The basic structure of the reduction in that paper can be accomplished with the following 3 steps:

1. Create many copies of a particular graph $H\_{n,p}$.
2. Identify certain pieces of some copies of $H\_{n,p}$ with each other (i.e. merge vertices/edges between multiple different copies of $H\_{n,p}$).
3. Remove certain vertices/edges from some copies.

The graph $H\_{n,p}$ has as its vertices the set of length-$n$ vectors modulo $p$ for which the components add to $0$ mod $p$. The edges connect every two vertices that differ in only two components with differences of $+1$ and $-1$ in those two components.

I propose the following coloring for this graph: assign a color to each edge according to its direction. If $x$ and $y$ are adjacent vertices, then $x-y$ is a vector with $n-2$ components equal to $0$, one component equal to $1$ and one component equal to $-1$. In other words, for every edge $(x, y)$ there are ${n \choose 2}$ options for which components of $x-y$ are non-zero. If we assign a unique color to each of these options then we have a coloring for all the edges such that every edge in the same direction has the same color. It is pretty easy to verify that no two edges in a $K\_n$ in $H\_{n,p}$ are in the same direction. Therefore every $K\_n$ in $H\_{n,p}$ is a rainbow $K\_n$ under this coloring.

When we follow the reduction, we use this coloring for every copy of $H\_{n,p}$. Therefore at the end of step 1 in the list above, every $K\_n$ in the graph is a rainbow $K\_n$.

In step 2 of the above list, we identify some vertices/edges with each other. In particular, in the reduction we always identify a $K\_n$ with another $K\_n$. But in this situation (where all the $K\_n$s are from a copy of $H\_{n,p}$), every $K\_n$ is either a translation of the "standard $K\_n$" which the paper calls $K$ or a translation of $-K$. Therefore, we are either identifying two parallel $K\_n$s or two $K\_n$s that are "flips" of each other. In either case, the edges that are identified across the two $K\_n$s are parallel and are therefore the same color. For example, see Figure 2 in the paper; edges that are identified are always parallel. Thus, since we never try to identify two edges of different colors, the coloring at the end of step 1 in the above list can be naturally extended into a coloring at the end of step 2. Identifying certain vertices/edges together doesn't create any new $K\_n$s, so it is still the case at the end of this step that every $K\_n$ is a rainbow $K\_n$.

Finally in step 3 we remove some vertices/edges, which also doesn't create any new $K\_n$s. Thus, we have our desired property: under the coloring I provided, every $K\_n$ in the graph generated by this reduction is a rainbow $K\_n$.


---

